Cho một số nguyên dương ~n~. Với mỗi thao tác, bạn đặt ~n = \lfloor \sqrt{n} \rfloor~, với ~\lfloor i \rfloor~ là số nguyên lớn nhất không vượt quá ~i~. Đếm số thao tác để có ~n = 1~. Bạn cần phải xử lý nhiều bộ dữ liệu như vậy.

Dữ liệu vào

• Dòng đầu tiên gồm một số nguyên dương ~t~ ~(1 \le t \le 10^5)~ - số bộ dữ liệu.
• ~t~ dòng tiếp theo, mõi dòng gồm một số nguyên dương ~n~ ~(1 \le n \le 10^{18})~.

Dữ liệu ra

• Gồm ~t~ dòng, dòng thứ ~i~ là kết quả của bộ dữ liệu thứ ~i~.

Ví dụ

Ví dụ 1

Dữ liệu vào

2
10
20

Dữ liệu ra

2
3

Giải thích

• Với bộ dữ liệu đầu tiên, ~\lfloor \sqrt{10} \rfloor = 3~ và ~\lfloor \sqrt{3} \rfloor = 1~.
• Với bộ dữ liệu thứ hai, ~\lfloor \sqrt{20} \rfloor = 4~, ~\lfloor \sqrt{4} \rfloor = 2~ và ~\lfloor \sqrt{2} \rfloor = 1~.

Cho một dãy số nguyên không âm ~a_1, a_2, ..., a_n~. Một cặp số ~(i, j)~ được gọi là cặp đôi "tam giác căn" khi và chỉ khi ~(\sqrt{i}, \sqrt{j}, \sqrt{i + j})~ là bộ ba cạnh của một tam giác. Nhiệm vụ của bạn là đếm số cặp vị trí ~1 \le u \le v \le n~ mà ~(a_u, a_v)~ là một cặp đôi "tam giác căn".

Dữ liệu vào

• Dòng đầu tiên gồm một số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng tiếp theo gồm ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le 10^{18})~.

Dữ liệu ra

• Một dòng duy nhất là phần dư của kết quả bài toán sau khi chia cho ~10^9 + 7~.

Ví dụ

Ví dụ 1

Dữ liệu vào

2
1 2

Dữ liệu ra

3

Giải thích

• Hình trên là ví dụ về các tam giác có các bộ số cạnh ~(1, 1, \sqrt{2}), (1, \sqrt{2}, \sqrt{3})~ và ~(\sqrt{2}, \sqrt{2}, 2)~.

Subtask 1 và 2 của bài này có đôi chút khác biệt về giới hạn của các biến nên hãy đọc kỹ đề. Với subtask 1, ~n, m \le 1000~ và ~0 \le v_i \le 1~.

Nhiệm vụ của bạn là tìm một dãy ~a~ gồm ~n~ phần tử thỏa mãn ~m~ yêu cầu. Trong đó yêu cầu thứ ~i~ có dạng ~l_i~ ~r_i~ ~v_i~, nghĩa là:

• Giá trị của ~a_{l_i}~ ~\&~ ~a_{l_i+1}~ ~\&~ ... ~\&~ ~a_{r_i}~ là chính xác ~v_i~, với ~\&~ là phép toán thao tác bit AND.

Dữ liệu vào

• Dòng đầu tiên gồm ~2~ số nguyên dương ~n, m~ ~(1 \le n, m \le 1000)~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm ~3~ số ~l_i~ ~r_i~ ~v_i~ ~(1 \le l_i \le r_i \le n; 0 \le v_i \le 1)~.

Dữ liệu ra

• In ra dãy ~a~ thỏa mãn với ~0 \le a_i < 2^{30}~. Nếu có nhiều kết quả, hãy in ra kết quả bất kỳ.
• Dữ liệu đầu vào đảm bảo luôn tồn tại kết quả.

Ví dụ

Dữ liệu vào

8 3
2 3 1
5 8 0
7 7 1

Dữ liệu ra

2 1 3 7 1 4 1 2

Giải thích

Với dãy ~a = [2, 1, 3, 7, 1, 4, 1, 2]~, ta có:

• Yêu cầu ~l = 7, r = 7~: ~a_7~ ~=~ ~1~.
• Yêu cầu ~l = 2, r = 3~: ~a_2~ ~\&~ ~a_3~ ~=~ ~1~.
• Yêu cầu ~l = 5, r = 8~: ~a_5~ ~\&~ ~a_6~ ~\&~ ~a_7~ ~\&~ ~a_8~ ~=~ ~0~.

Qua đó, ta thấy dãy ~a~ trên là dãy ~a~ thỏa mãn tất cả ~m~ yêu cầu.

Subtask 1 và 2 của bài này có đôi chút khác biệt về giới hạn của các biến. Các bạn lưu ý đọc kỹ đề. Với subtask 2, không có giới hạn gì thêm.

Nhiệm vụ của bạn là tìm một dãy ~a~ gồm ~n~ phần tử thỏa mãn ~m~ yêu cầu. Trong đó yêu cầu thứ ~i~ có dạng ~l_i~ ~r_i~ ~v_i~, nghĩa là:

• Giá trị của ~a_{l_i}~ ~\&~ ~a_{l_i+1}~ ~\&~ ... ~\&~ ~a_{r_i}~ là chính xác ~v_i~, với ~\&~ là phép toán thao tác bit AND.

Dữ liệu vào

• Dòng đầu tiên gồm ~2~ số nguyên dương ~n, m~ ~(1 \le n, m \le 10^5)~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm ~3~ số ~l_i~ ~r_i~ ~v_i~ ~(1 \le l_i \le r_i \le n; 0 \le v_i < 2^{30})~.

Dữ liệu ra

• In ra dãy ~a~ thỏa mãn với ~0 \le a_i < 2^{30}~. Nếu có nhiều kết quả, hãy in ra kết quả bất kỳ.
• Dữ liệu đầu vào đảm bảo luôn tồn tại kết quả.

Ví dụ

Dữ liệu vào

8 4
2 4 1
6 8 6
3 7 2
1 1 5

Dữ liệu ra

5 1 5 3 2 7 6 7

Giải thích

Với dãy ~a = [5, 1, 5, 3, 2, 7, 6, 7]~, ta có:

• Yêu cầu ~l = 1, r = 1~: ~a_1~ ~=~ ~5~.
• Yêu cầu ~l = 2, r = 4~: ~a_2~ ~\&~ ~a_3~ ~\&~ ~a_4~ ~=~ ~1~ ~\&~ ~5~ ~\&~ ~3~ ~=~ ~1~.
• Yêu cầu ~l = 6, r = 8~: ~a_6~ ~\&~ ~a_7~ ~\&~ ~a_8~ ~=~ ~7~ ~\&~ ~6~ ~\&~ ~7~ ~=~ ~6~.
• Yêu cầu ~l = 3, r = 7~: ~a_3~ ~\&~ ~a_4~ ~\&~ ~a_5~ ~\&~ ~a_6~ ~\&~ ~a_7~ ~=~ ~5~ ~\&~ ~3~ ~\&~ ~2~ ~\&~ ~7~ ~\&~ ~6~ ~=~ ~2~.

Qua đó, ta thấy dãy ~a~ trên là dãy ~a~ thỏa mãn tất cả ~m~ yêu cầu.

Một cặp số ~(a, b)~ có độ đẹp được tính bằng công thức ~\lfloor \frac{a}{b} \rfloor + a \mod b~, với ~\lfloor a \rfloor~ là số nguyên lớn nhất không vượt quá ~a~. Tìm một cặp số ~(a, b)~ với ~2 \le a, b \le 10^9~ có độ đẹp bằng ~k~.

Dữ liệu

• Dòng đầu tiên gồm số nguyên dương ~T~ là số bộ dữ liệu ~(1 \le T \le 1000)~.
• ~T~ dòng tiếp theo, mỗi dòng gồm một số nguyên dương ~k~ ~(1 \le k \le 10^9)~.

Kết quả

• Với mỗi bộ dữ liệu, in ra hai số nguyên dương ~a, b~ thỏa mãn nếu tìm được. Ngược lại, in ra -1 -1.

Ví dụ

Dữ liệu

3
2
3
4

Kết quả

3 2
5 3
8 2

Giải thích

• Ở bộ dữ liệu đầu tiên, ~\lfloor \frac{5}{5} \rfloor + 5 \mod 5 = 1 + 0 = 1~.
• Ở bộ dữ liệu thứ hai, ~\lfloor \frac{3}{2} \rfloor + 3 \mod 2 = 1 + 1 = 2~.
• Ở bộ dữ liệu thứ ba, ~\lfloor \frac{5}{3} \rfloor + 5 \mod 3 = 1 + 2 = 3~.

Alice có một bảng ký tự kích thước ~n \times m~. Alice vẽ một đường đi ngẫu nhiên trên bảng sao cho hai ô liên tiếp trên đường đi có chung cạnh và không có ô nào xuất hiện hai lần trên đường đi. Cô ghi lại các ký tự xuất hiện trên đường đi đó theo thứ tự từ điểm đầu đến điểm cuối, sau đó xóa đường đi mà cô đã vẽ khỏi bảng. Cô đưa bảng ký tự và chuỗi ký tự vừa tìm được cho Bob và đố Bob tìm ra một đường đi mà cô đã vẽ. Các bạn hãy giúp Bob tòm đường đi thỏa mãn nhé.

Dữ liệu

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ ~(1 \le n, m \le 5)~.
• Dòng tiếp theo gồm một chuỗi ký tự ~s~ gồm các chữ cái tiếng Anh in thường là từ mà Alice đưa cho Bob. Độ dài xâu ~s~ không quá ~15~.
• ~n~ dòng tiếp theo, mỗi dòng gồm một chuỗi ~m~ ký tự tiếng Anh in thường.
• Dữ liệu đầu vào đảm bảo tồn tại đường đi thỏa mãn.

Kết quả

• Gồm nhiều dòng, dòng thứ ~i~ tương ứng với vị trí của ký tự thứ ~i~ trong ~s~.

Ví dụ

Dữ liệu

3 5
dine
sqrto
nline
judge

Kết quả

3 3
2 3
2 4
2 5

Một cửa hàng đá quý có bán một chuỗi ngọc trang sức gồm ~n~ viên ngọc màu đỏ ở bên trái và ~m~ viên ngọc màu xanh ở bên phải (chuỗi ngọc này là chuỗi thẳng, không phải vòng tròn). Alice muốn mua rất nhiêu chuỗi ngọc như vậy để kết thành một chuỗi dài duy nhất. Cô muốn biết trong ~k~ viên ngọc đầu tiên của chuỗi thu được có bao nhiêu viên ngọc màu đỏ và bao nhiêu viên ngọc màu xanh. Các bạn hãy tính giúp Alice nhé.

Dữ liệu

• Một dòng duy nhất gồm ba số nguyên dương ~n, m, k~ ~(1 \le n, m, k \le 10^9)~.

Kết quả

• Một dòng duy nhất gồm hai số nguyên là số viên ngọc màu đỏ và màu xanh.

Ví dụ

Dữ liệu

4 2 6

Kết quả

4 2