Giải hệ phương trình: $$ \begin{align} a_{11} x_1 + a_{12} x_2 + &\dots + a_{1m} x_m = b_1 \\ a_{21} x_1 + a_{22} x_2 + &\dots + a_{2m} x_m = b_2 \\ &\vdots \\ a_{n1} x_1 + a_{n2} x_2 + &\dots + a_{nm} x_m = b_n \end{align} $$

INPUT

• Dòng đầu gồm ~2~ số ~n~, ~m~ ~(0 < n, m \leqslant 100)~ lần lượt là số lượng phương trình và số ẩn.
• ~n~ dòng sau, mỗi dòng là ~1~ phương trình có dạng :
  • ~m~ số đầu tiên là hệ số ~a_{ij}~.
  • sau đó là hệ số ~b_i~.

OUTPUT

• Dòng đầu là số lượng nghiệm:
  • ~0~: hệ vô nghiệm.
  • ~1~: hệ có ~1~ nghiệm duy nhất.
  • ~2~: hệ có vô số nghiệm.
• Nếu hệ có ít nhất ~1~ nghiệm, dòng tiếp theo hãy in ra ~m~ số là nghiệm bất kì với 15 chữ số thập phân sau dấu phẩy.

SAMPLE TEST

Input:

5 5
-0.401478194815231 -0.671289386920888 -1.839630600661053 1.044918393550852 -0.715327873665762 4.559893472213569
9.889242013045755 -1.062434216105394 -0.334141109212244 1.031059261429236 -0.588239880357510 -41.038569602897400
-4.622099934474900 0.894723386016340 -0.929532017337562 -0.337534248882405 2.155326625139754 18.492862680859524
-0.141885993213340 -3.388798089268028 -0.258109178922436 15.212744479495268 0.852329454855465 -3.662991388094354
0.271735106692403 1.323363367969020 -3.170154753587526 -0.142209502157441 1.833660372050498 -3.763279263429966

Output:

-4.478839836674546 -4.088073957138477 -0.759532442670690 -1.214758714286829 0.154445428691314 

Cho đồ thị vô hướng và số nguyên tố ~p~, mỗi đỉnh có trọng số ~x_i~ ~(0 \leqslant x_i < p)~. Mỗi đỉnh ~u~ sẽ có một số nguyên ~b_u~ ~(0 \leqslant b_u < p)~ thỏa mãn ~b_u = \Sigma x_v (mod~ ~p)~ với tất cả các đỉnh ~v~ có cạnh nối trực tiếp với ~u~.

Yêu cầu: Cho đồ thị và mảng ~b~ ~(0 \leqslant b_i < p)~, hãy đếm số lượng mảng ~x~ thỏa mãn. Dữ liệu đảm bảo tồn tại ít nhất ~1~ nghiệm thỏa mãn.

INPUT

• Dòng đầu chứa 3 số nguyên ~n~, ~m~, ~p~ ~(1 \leqslant n \leqslant 100,~ ~1 \leqslant m \leqslant 200,~ ~p \leqslant 10 ^ 9)~ lần lượt là số đỉnh, số cạnh và số nguyên tố ~p~.
• Dòng tiếp theo là ~n~ số nguyên của mảng ~b~, mỗi số cách nhau ~1~ dấu cách.
• ~m~ dòng sau, mỗi dòng là ~2~ số ~u~, ~v~ cho biết có cạnh nối giữa ~u~ và ~v~.

OUTPUT

• Một số nguyên duy nhất là số lượng mảng ~x~ thỏa mãn lấy dư cho ~10^9+7~.

SAMPLE TEST

Input:

5 5 13
5 20 0 23 5 
1 4
2 1
2 4
4 5
5 2

Output:

169

Giám khảo bí mật chọn một đa thức bậc không quá ~k~ trên modulo ~M = 10^6 + 3~ (với ~M~ là số nguyên tố):

~ f(x)=a_0 + a_1x + a_2x^2 + \cdots + a_kx^k ~

Trong đó:

• ~0 \le k \le 10~
• ~a_i~ là số nguyên, ~0 \le a_i < M~
• Tồn tại ít nhất một ~i~ sao cho ~a_i > 0~ (không phải đa thức ~0~).

Bạn không biết các hệ số ~a_i~. Nhiệm vụ của bạn là tìm một số nguyên ~x_0~ sao cho:

~ f(x_0)\equiv 0 \pmod{M} ~

Nếu không tồn tại ~x_0~ nào trong ~[0, M-1]~ thỏa mãn, hãy in ra ~-1~.

Tương tác

Bạn được phép hỏi tối đa 50 truy vấn.

Truy vấn

Mỗi lần bạn in:

• ? x

với ~x\in \mathbb{Z}~, ~0 \le x < M~.

Sau đó flush output (dùng endl hoặc cout << '\n' << flush).

Máy chấm sẽ trả về một số nguyên:

• ~f(x) \bmod M~.

Nếu bạn in truy vấn không hợp lệ, máy chấm có thể trả về -1. Khi nhận -1, bạn phải thoát ngay.

Kết thúc

Khi bạn đã quyết định đáp án, in:

• ! x0

Trong đó:

• ~x_0~ là nghiệm bạn tìm được, ~0 \le x_0 < M~, hoặc
• -1 nếu bạn tin rằng không có nghiệm.

In xong cũng phải flush.

Giới hạn

• ~M = 10^6 + 3~
• ~k \le 10~
• Số truy vấn ~\le 50~

Ví dụ minh hoạ (giải thích)

Giả sử giám khảo chọn ~f(x)=1+2x+3x^2 \pmod{M}~.

Máy chấm không cho bạn biết hệ số, nhưng nếu bạn hỏi:

? 0

máy chấm trả:

1

vì ~f(0)=1~.

Nếu bạn hỏi tiếp:

? 1

máy chấm trả:

6

vì ~f(1)=6~.

Bạn tiếp tục hỏi các điểm khác (tối đa 50 lần), rồi cuối cùng in:

! x0

với ~x0~ là nghiệm tìm được, hoặc -1 nếu không có.

Lưu ý

• Mỗi truy vấn phải đúng cú pháp ? x.
• Luôn flush sau mỗi lần in truy vấn/đáp án.
• Không được in thêm dữ liệu ngoài format tương tác.

Cho một dãy số nguyên không âm ~a~ gồm ~n~ phần tử.

Gọi ~{s_1, s_2, \ldots, s_k}~ (~s_1 < s_2 < \cdots < s_k~) là tập hợp tất cả các số nguyên không âm có thể là kết quả của phép XOR của một dãy con (không nhất thiết liên tiếp và có thể rỗng) của ~a~.

Cho hai số nguyên ~L~ và ~R~, hãy in ra ~s_L, s_{L+1}, \ldots, s_R~ theo thứ tự này.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~N~, ~L~ và ~R~ (~1 \leq N \le 2 \times 10^5, 1 \le L \le R \le k~, ~R - L + 1 \le 2 \times 10^5~).
• Dòng thứ hai gồm ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~. ~(0 \le a_i \le 10^{18})~.

Output

• In ra ~s_i~ ~(1 \le L \le i \le R)~ theo thứ tự tăng dần của ~i~.

Subtask

• Subtask ~1~: ~n \le 1000, a_i \le 1000~ ~(30\%)~
• Subtask ~2~: ~L = R = k~ ~(30\%)~
• Subtask ~3~: Không giới hạn gì thêm. ~(40\%)~

Sample

Input 1

4 1 8
14 5 14 6

Output 1

0 3 5 6 8 11 13 14

Một dãy ~b~ được định nghĩa là độc lập chính phương nếu như không tồn tại bất kì dãy con khác rỗng nào của ~b~ có tích là một số chính phương.

Cho dãy ~a~ gồm ~n~ phần tử nguyên dương, hãy tìm dãy con dài nhất của ~a~ sao cho nó độc lập chính phương.

Input

• Dòng đầu tiên gồm một số nguyên ~n~ (~1 \le n \le 1000~)— độ dài của dãy ~a~.

• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, a_3, \dots ,a_n~ (~1 \le a_i \le 10^4~).

Output

• In ra độ dài của dãy con dài nhất của ~a~ sao cho dãy này độc lập chính phương.

Scoring

Sample Input 1

4
5 6 4 30

Sample Output 1

2

Sau bao năm vất vả học tập và giải những bài toán khó của Alice, Bob bây giờ đã là một quản lý của một công ty lớn. Một ngày đẹp trời nọ, Alice quyết định thăm Bob và cho Bob một bài toán khác để thử thách cậu.

Giả sử công ty của Bob gồm ~n~ nhân viên được đánh chỉ số từ ~1~ đến ~n~ và người thứ ~i~ có năng lực là ~a_i~. Một đội là một nhóm các nhân viên và năng lực của đội đó là tổng XOR (exclusive or) của năng lực của mọi người trong đội. Alice sẽ đưa ra tổng cộng ~q~ yêu cầu, mỗi yêu cầu thuộc một trong hai loại sau:

1. Thay đổi năng lực của nhân viên thứ ~i~ thành ~x~.
2. Đếm số cách chọn một đội mà mỗi nhân viên có chỉ số nằm trong đoạn ~[l, r]~ và năng lực của đội đúng bằng ~s~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(1 \leq n, q \leq 5 \times 10^{4})~ là số lượng nhân viên trong công ty của Bob và số lượng yêu cầu của Alice.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_{1}, a_{2}, \ldots, a_n~ ~(1 \leq a_{i} \leq 10^{6})~ là năng lực của các nhân viên.
• Trong ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~1~ hoặc ~2~. Số ~1~ theo sau bởi hai số nguyên ~i~ và ~x~ ~(1 \leq i \leq n, 1 \leq x \leq 10^{6})~ mô tả yêu cầu loại ~1~. Số ~2~ theo sau bởi ba số nguyên ~l~, ~r~ và ~s~ ~(1 \leq l \leq r \leq n~, ~1 \leq s \leq 10^{6})~ mô tả yêu cầu loại ~2~.

Output

• Đối với mỗi yêu cầu loại ~2~, in ra một số nguyên trên một dòng là phần dư của số cách chọn thỏa mãn khi chia cho ~10^{9} + 7~.

Scoring

• Subtask ~1~ (~20\%~ số điểm): ~n, q \leq 20~.
• Subtask ~2~ (~20\%~ số điểm): ~n \leq 10^{3}~, ~a_i \leq 10^{3}~, không có yêu cầu loại ~1~ và mọi yêu cầu loại ~2~ đều có ~l = 1~.
• Subtask ~3~ (~30\%~ số điểm): ~n, q \leq 10^{3}~.
• Subtask ~4~ (~30\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

3 3 1 2 3 2 1 3 3 2 1 2 3 2 1 3 1

Sample Output 1

2
1
2

Ẽplanation

• Yêu cầu thứ nhất trong đoạn ~[1, 3]~ có ~2~ cách chọn đội là: ~[1, 2], [3]~.
• Yêu cầu thứ hai trong đoạn ~[1, 2]~ có ~1~ cách chọn đội là: ~[1, 2]~.
• Yêu cầu thứ ba trong đoạn ~[1, 3]~ có ~2~ cách chọn đội là: ~[1], [2, 3]~.