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.

Các subtask 1, 2, 3, 4 của bài này sẽ có đôi chút khác biệt về yêu cầu đề và giới hạn của các biến. Các bạn lưu ý đọc kỹ đề. Với subtask 1, ~q = 1~.

Quang đang chơi một trò chơi điện tử. Màn chơi hiện tại của Quang có ~n~ cứ điểm được xếp thành một đường thẳng. Nhân vật của Quang có hai chỉ số là thể lực, ký hiệu là ~p~, và máu, ký hiệu là ~h~. Anh ta sẽ thăm các cứ điểm theo thứ tự tăng dần (nghĩa là sau khi thăm cứ điểm thứ ~i~ anh ta sẽ di chuyển đến cứ điểm thứ ~i + 1~). Cứ điểm thứ ~i~ có thể thuộc một trong ba loại sau:

• Cứ điểm loại ~1~: chứa một vật phẩm giúp nhân vật của Quang tăng thêm ~1~ điểm thể lực.
• Cứ điểm loại ~2~: chứa một vật phẩm giúp nhân vật của Quang tăng thêm ~1~ máu.
• Cứ điểm loại ~3~: chứa một con quái vật. Nhân vật của Quang sẽ có hai lựa chọn:
  • Chiến đấu với quái vật và mất ~1~ điểm thể lực.
  • Chấp nhận để quái vật đánh một đòn, mất ~1~ máu và chạy trốn khỏi cứ điểm.

Nếu một trong hai chỉ số máu và thể lực của nhân vật về ~0~ tại một thời điểm nào đó, nhân vật của Quang sẽ chết và Quang sẽ thua trò chơi.

Quang có ~q~ kịch bản, trong đó kịch bản thứ ~i~ cho biết nhân vật của Quang đang chuẩn bị thăm cứ điểm ~l_i~, đang có ~p_i~ điểm thể lực và ~h_i~ máu. Bạn cần tính toán xem nhân vật của Quang có thể an toàn thoát khỏi cứ điểm ~r_i~ hay không. Nếu có, hãy cho biết số quái vật ít nhất mà nhân vật của Quang phải chiến đấu là bao nhiêu.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên dương, ~n, q~ ~(1 \le n \le 10^5, q = 1)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 3)~ - loại của cứ điểm thứ ~i~.
• ~q~ dòng tiếp theo, mỗi dòng gồm bốn số nguyên dương ~l_i, r_i, p_i, h_i~ ~(1 \le l_i \le r_i \le n, 1 \le p_i, h_i \le 10^5)~.

Dữ liệu ra

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.
  • Nếu nhân vật của Quang không thể đi từ ~l_i~ đến ~r_i~, in ra ~-1~.
  • Ngược lại, in ra số quái vật nhỏ nhất mà nhân vật của Quang phải chiến đấu.

Ví dụ

Ví dụ 1

Dữ liệu vào

5 1
2 2 3 1 3
1 5 1 1

Dữ liệu ra

0

Giải thích

• Trong kịch bản đầu tiên, sau khi được tăng thêm ~2~ máu ở cứ điểm thứ ~1~ và ~2~, nhân vật của Quang chỉ cần tránh hai quái vật ở nhà ~3~ và ~5~ rồi thoát khỏi cứ điểm ~5~ mà không cần phải chiến đấu với một con quái vật nào.

Các subtask 1, 2, 3, 4 của bài này sẽ có đôi chút khác biệt về yêu cầu đề và giới hạn của các biến. Các bạn lưu ý đọc kỹ đề. Với subtask 2, có không quá ~500~ cứ điểm loại ~3~.

Quang đang chơi một trò chơi điện tử. Màn chơi hiện tại của Quang có ~n~ cứ điểm được xếp thành một đường thẳng. Nhân vật của Quang có hai chỉ số là thể lực, ký hiệu là ~p~, và máu, ký hiệu là ~h~. Anh ta sẽ thăm các cứ điểm theo thứ tự tăng dần (nghĩa là sau khi thăm cứ điểm thứ ~i~ anh ta sẽ di chuyển đến cứ điểm thứ ~i + 1~). Cứ điểm thứ ~i~ có thể thuộc một trong ba loại sau:

• Cứ điểm loại ~1~: chứa một vật phẩm giúp nhân vật của Quang tăng thêm ~1~ điểm thể lực.
• Cứ điểm loại ~2~: chứa một vật phẩm giúp nhân vật của Quang tăng thêm ~1~ máu.
• Cứ điểm loại ~3~: chứa một con quái vật. Nhân vật của Quang sẽ có hai lựa chọn:
  • Chiến đấu với quái vật và mất ~1~ điểm thể lực.
  • Chấp nhận để quái vật đánh một đòn, mất ~1~ máu và chạy trốn khỏi cứ điểm.

Nếu một trong hai chỉ số máu và thể lực của nhân vật về ~0~ tại một thời điểm nào đó, nhân vật của Quang sẽ chết và Quang sẽ thua trò chơi.

Quang có ~q~ kịch bản, trong đó kịch bản thứ ~i~ cho biết nhân vật của Quang đang chuẩn bị thăm cứ điểm ~l_i~, đang có ~p_i~ điểm thể lực và ~h_i~ máu. Bạn cần tính toán xem nhân vật của Quang có thể an toàn thoát khỏi cứ điểm ~r_i~ hay không. Nếu có, hãy cho biết số quái vật ít nhất mà nhân vật của Quang phải chiến đấu là bao nhiêu.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên dương, ~n, q~ ~(1 \le n, q \le 10^5)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 3)~ - loại của cứ điểm thứ ~i~.
• ~q~ dòng tiếp theo, mỗi dòng gồm bốn số nguyên dương ~l_i, r_i, p_i, h_i~ ~(1 \le l_i \le r_i \le n, 1 \le p_i, h_i \le 10^5)~.
• Với subtask 2, có không quá ~500~ cứ điểm loại ~3~.

Dữ liệu ra

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.
  • Nếu nhân vật của Quang không thể đi từ ~l_i~ đến ~r_i~, in ra ~-1~.
  • Ngược lại, in ra số quái vật nhỏ nhất mà nhân vật của Quang phải chiến đấu.

Ví dụ

Ví dụ 1

Dữ liệu vào

5 3
2 2 3 1 3
1 5 1 1
3 5 1 1
4 5 1 1

Dữ liệu ra

0
-1
1

Giải thích

• Trong kịch bản đầu tiên, sau khi được tăng thêm ~2~ máu ở cứ điểm thứ ~1~ và ~2~, nhân vật của Quang chỉ cần tránh hai quái vật ở nhà ~3~ và ~5~ rồi thoát khỏi cứ điểm ~5~ mà không cần phải chiến đấu với một con quái vật nào.
• Trong kịch bàn thứ hai, cho dù Quang chọn chiến đấu hay chạy trốn thì máu hoặc thể lực của nhân vật đều về ~0~ và Quang thua trò chơi.
• Trong kịch bản cuối cùng, Quang nhận ~1~ điểm thể lực ở cứ điểm ~4~ và chiến đấu với quái vật ở cứ điểm ~5~. Do đó nhân vật của Quang phải đối đầu với ~1~ quái vật.

Các subtask 1, 2, 3, 4 của bài này sẽ có đôi chút khác biệt về yêu cầu đề và giới hạn của các biến. Các bạn lưu ý đọc kỹ đề. Với subtask 3, bạn chỉ cần xác định xem nhân vật của Quang có thể đi từ cứ điểm ~l_i~ đến ~r_i~ hay không.

Quang đang chơi một trò chơi điện tử. Màn chơi hiện tại của Quang có ~n~ cứ điểm được xếp thành một đường thẳng. Nhân vật của Quang có hai chỉ số là thể lực, ký hiệu là ~p~, và máu, ký hiệu là ~h~. Anh ta sẽ thăm các cứ điểm theo thứ tự tăng dần (nghĩa là sau khi thăm cứ điểm thứ ~i~ anh ta sẽ di chuyển đến cứ điểm thứ ~i + 1~). Cứ điểm thứ ~i~ có thể thuộc một trong ba loại sau:

• Cứ điểm loại ~1~: chứa một vật phẩm giúp nhân vật của Quang tăng thêm ~1~ điểm thể lực.
• Cứ điểm loại ~2~: chứa một vật phẩm giúp nhân vật của Quang tăng thêm ~1~ máu.
• Cứ điểm loại ~3~: chứa một con quái vật. Nhân vật của Quang sẽ có hai lựa chọn:
  • Chiến đấu với quái vật và mất ~1~ điểm thể lực.
  • Chấp nhận để quái vật đánh một đòn, mất ~1~ máu và chạy trốn khỏi cứ điểm.

Nếu một trong hai chỉ số máu và thể lực của nhân vật về ~0~ tại một thời điểm nào đó, nhân vật của Quang sẽ chết và Quang sẽ thua trò chơi.

Quang có ~q~ kịch bản, trong đó kịch bản thứ ~i~ cho biết nhân vật của Quang đang chuẩn bị thăm cứ điểm ~l_i~, đang có ~p_i~ điểm thể lực và ~h_i~ máu. Bạn cần tính toán xem nhân vật của Quang có thể an toàn thoát khỏi cứ điểm ~r_i~ hay không.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên dương, ~n, q~ ~(1 \le n, q \le 10^5)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 3)~ - loại của cứ điểm thứ ~i~.
• ~q~ dòng tiếp theo, mỗi dòng gồm bốn số nguyên dương ~l_i, r_i, p_i, h_i~ ~(1 \le l_i \le r_i \le n, 1 \le p_i, h_i \le 10^5)~.

Dữ liệu ra

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.
  • Nếu nhân vật của Quang không thể đi từ ~l_i~ đến ~r_i~, in ra ~-1~.
  • Ngược lại, in ra ~0~.

Ví dụ

Ví dụ 1

Dữ liệu vào

5 3
2 2 3 1 3
1 5 1 1
3 5 1 1
4 5 1 1

Dữ liệu ra

0
-1
0

Giải thích

• Trong kịch bản đầu tiên, sau khi được tăng thêm ~2~ máu ở cứ điểm thứ ~1~ và ~2~, nhân vật của Quang chỉ cần tránh hai quái vật ở nhà ~3~ và ~5~ rồi thoát khỏi cứ điểm ~5~ mà không cần phải chiến đấu với một con quái vật nào.
• Trong kịch bàn thứ hai, cho dù Quang chọn chiến đấu hay chạy trốn thì máu hoặc thể lực của nhân vật đều về ~0~ và Quang thua trò chơi.
• Trong kịch bản cuối cùng, Quang nhận ~1~ điểm thể lực ở cứ điểm ~4~ và chiến đấu với quái vật ở cứ điểm ~5~. Do đó nhân vật của Quang phải đối đầu với ~1~ quái vật.

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

Quang đang chơi một trò chơi điện tử. Màn chơi hiện tại của Quang có ~n~ cứ điểm được xếp thành một đường thẳng. Nhân vật của Quang có hai chỉ số là thể lực, ký hiệu là ~p~, và máu, ký hiệu là ~h~. Anh ta sẽ thăm các cứ điểm theo thứ tự tăng dần (nghĩa là sau khi thăm cứ điểm thứ ~i~ anh ta sẽ di chuyển đến cứ điểm thứ ~i + 1~). Cứ điểm thứ ~i~ có thể thuộc một trong ba loại sau:

• Cứ điểm loại ~1~: chứa một vật phẩm giúp nhân vật của Quang tăng thêm ~1~ điểm thể lực.
• Cứ điểm loại ~2~: chứa một vật phẩm giúp nhân vật của Quang tăng thêm ~1~ máu.
• Cứ điểm loại ~3~: chứa một con quái vật. Nhân vật của Quang sẽ có hai lựa chọn:
  • Chiến đấu với quái vật và mất ~1~ điểm thể lực.
  • Chấp nhận để quái vật đánh một đòn, mất ~1~ máu và chạy trốn khỏi cứ điểm.

Nếu một trong hai chỉ số máu và thể lực của nhân vật về ~0~ tại một thời điểm nào đó, nhân vật của Quang sẽ chết và Quang sẽ thua trò chơi.

Quang có ~q~ kịch bản, trong đó kịch bản thứ ~i~ cho biết nhân vật của Quang đang chuẩn bị thăm cứ điểm ~l_i~, đang có ~p_i~ điểm thể lực và ~h_i~ máu. Bạn cần tính toán xem nhân vật của Quang có thể an toàn thoát khỏi cứ điểm ~r_i~ hay không. Nếu có, hãy cho biết số quái vật ít nhất mà nhân vật của Quang phải chiến đấu là bao nhiêu.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên dương, ~n, q~ ~(1 \le n, q \le 10^5)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 3)~ - loại của cứ điểm thứ ~i~.
• ~q~ dòng tiếp theo, mỗi dòng gồm bốn số nguyên dương ~l_i, r_i, p_i, h_i~ ~(1 \le l_i \le r_i \le n, 1 \le p_i, h_i \le 10^5)~.
• Với subtask 4, không có giới hạn gì thêm.

Dữ liệu ra

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.
  • Nếu nhân vật của Quang không thể đi từ ~l_i~ đến ~r_i~, in ra ~-1~.
  • Ngược lại, in ra số quái vật nhỏ nhất mà nhân vật của Quang phải chiến đấu.

Ví dụ

Ví dụ 1

Dữ liệu vào

5 3
2 2 3 1 3
1 5 1 1
3 5 1 1
4 5 1 1

Dữ liệu ra

0
-1
1

Giải thích

• Trong kịch bản đầu tiên, sau khi được tăng thêm ~2~ thể ở cứ điểm thứ ~1~ và ~2~, nhân vật của Quang chỉ cần tránh hai quái vật ở nhà ~3~ và ~5~ rồi thoát khỏi cứ điểm ~5~ mà không cần phải chiến đấu với một con quái vật nào.
• Trong kịch bàn thứ hai, cho dù Quang chọn chiến đấu hay chạy trốn thì máu hoặc thể lực của nhân vật đều về ~0~ và Quang thua trò chơi.
• Trong kịch bản cuối cùng, Quang nhận ~1~ điểm thể lực ở cứ điểm ~4~ và chiến đấu với quái vật ở cứ điểm ~5~. Do đó nhân vật của Quang phải đối đầu với ~1~ quái vật.

Các subtask 1, 2, 3, 4 của bài này sẽ 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 1, ~|s|, q \le 200~.

Bạn được cho một xâu ~s~ gồm các chữ cái tiếng Anh viết thường, và ~q~ truy vấn có dạng ~(l, r)~. Với mỗi truy vấn, bạn cần đếm xem có bao nhiêu xâu con liên tiếp của xâu ~s_{(l ... r)}~ là xâu đối xứng (palindrome).

(~s_{(l ... r)}~ là xâu con gồm các ký tự từ ~l~ đến ~r~ của ~s~, ~|s|~ là độ dài của xâu ~s~)

Dữ liệu vào

• Dòng đầu tiên gồm xâu ~s~ có độ dài không quá ~200~.
• Dòng tiếp theo gồm một số nguyên dương ~q~ ~(q \le 200)~ - số truy vấn cần xử lý.
• ~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~l, r~ ~(1 \le l \le r \le |s|)~.

Dữ liệu ra

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Ví dụ

Ví dụ 1

Dữ liệu vào

abbab
5
1 3
1 4
1 5
2 5
3 5

Dữ liệu ra

4
6
8
6
4

Giải thích

• Các xâu đối xứng ở truy vấn thứ ~3~ là a (~2~ lần), b (~3~ lần), bb, abba, bab.

Các subtask 1, 2, 3, 4 của bài này sẽ 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, ~q \le 200~.

Bạn được cho một xâu ~s~ gồm các chữ cái tiếng Anh viết thường, và ~q~ truy vấn có dạng ~(l, r)~. Với mỗi truy vấn, bạn cần đếm xem có bao nhiêu xâu con liên tiếp của xâu ~s_{(l ... r)}~ là xâu đối xứng (palindrome).

(~s_{(l ... r)}~ là xâu con gồm các ký tự từ ~l~ đến ~r~ của ~s~, ~|s|~ là độ dài của xâu ~s~)

Dữ liệu vào

• Dòng đầu tiên gồm xâu ~s~ có độ dài không quá ~2 \times 10^5~.
• Dòng tiếp theo gồm một số nguyên dương ~q~ ~(q \le 200)~ - số truy vấn cần xử lý.
• ~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~l, r~ ~(1 \le l \le r \le |s|)~.

Dữ liệu ra

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Ví dụ

Ví dụ 1

Dữ liệu vào

abbab
5
1 3
1 4
1 5
2 5
3 5

Dữ liệu ra

4
6
8
6
4

Giải thích

• Các xâu đối xứng ở truy vấn thứ ~3~ là a (~2~ lần), b (~3~ lần), bb, abba, bab.

Các subtask 1, 2, 3, 4 của bài này sẽ 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 3, ~n \le 5000~.

Giới hạn thời gian dành cho subtask 3 là ~1.5~ giây.

Bạn được cho một xâu ~s~ gồm các chữ cái tiếng Anh viết thường, và ~q~ truy vấn có dạng ~(l, r)~. Với mỗi truy vấn, bạn cần đếm xem có bao nhiêu xâu con liên tiếp của xâu ~s_{(l ... r)}~ là xâu đối xứng (palindrome).

(~s_{(l ... r)}~ là xâu con gồm các ký tự từ ~l~ đến ~r~ của ~s~, ~|s|~ là độ dài của xâu ~s~)

Dữ liệu vào

• Dòng đầu tiên gồm xâu ~s~ có độ dài không quá ~5000~.
• Dòng tiếp theo gồm một số nguyên dương ~q~ ~(q \le 2 \times 10^5)~ - số truy vấn cần xử lý.
• ~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~l, r~ ~(1 \le l \le r \le |s|)~.

Dữ liệu ra

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Ví dụ

Ví dụ 1

Dữ liệu vào

abbab
5
1 3
1 4
1 5
2 5
3 5

Dữ liệu ra

4
6
8
6
4

Giải thích

• Các xâu đối xứng ở truy vấn thứ ~3~ là a (~2~ lần), b (~3~ lần), bb, abba, bab.

Các subtask 1, 2, 3, 4 của bài này sẽ 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 4, không có giới hạn gì thêm.

Giới hạn thời gian dành cho subtask 4 là ~3~ giây.

Bạn được cho một xâu ~s~ gồm các chữ cái tiếng Anh viết thường, và ~q~ truy vấn có dạng ~(l, r)~. Với mỗi truy vấn, bạn cần đếm xem có bao nhiêu xâu con liên tiếp của xâu ~s_{(l ... r)}~ là xâu đối xứng (palindrome).

(~s_{(l ... r)}~ là xâu con gồm các ký tự từ ~l~ đến ~r~ của ~s~, ~|s|~ là độ dài của xâu ~s~)

Dữ liệu vào

• Dòng đầu tiên gồm xâu ~s~ có độ dài không quá ~2 \times 10^5~.
• Dòng tiếp theo gồm một số nguyên dương ~q~ ~(q \le 2 \times 10^5)~ - số truy vấn cần xử lý.
• ~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~l, r~ ~(1 \le l \le r \le |s|)~.

Dữ liệu ra

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Ví dụ

Ví dụ 1

Dữ liệu vào

abbab
5
1 3
1 4
1 5
2 5
3 5

Dữ liệu ra

4
6
8
6
4

Giải thích

• Các xâu đối xứng ở truy vấn thứ ~3~ là a (~2~ lần), b (~3~ lần), bb, abba, bab.

Subtask 1, 2, 3 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 1, ~l_i = 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 ~S(l_i, r_i)~ ~=~ ~a_{l_i}~ ~\oplus~ ~a_{l_i+1}~ ~\oplus~ ... ~\oplus~ ~a_{r_i}~ là chính xác ~v_i~, với ~\oplus~ là phép toán thao tác bit XOR.

Input

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

Output

• In ra ~n~ dòng, dòng thứ ~p~ in ra giá trị của ~a_p~ và một số nguyên dương ~i~ trong đó giá trị của ~a_p~ chắc chắn xác định từ yêu cầu thứ ~i~ ~(1 \le i \le m)~. Trong trường hợp không thể, hãy in ra ~-1~ ~-1~.

Test

Input

4 3
1 3 0
1 2 3
1 4 4

Output

-1 -1
-1 -1
3 2
4 3

Note

Với yêu cầu thứ ~i = 1~, ta chỉ biết ~S(1, 3) = 0~ và không thể biết được điều gì. Đến với yêu cầu thứ ~i = 2~, ta có thể tính được ~a_3~ ~=~ ~S(1, 2)~ ~\oplus~ ~S(1, 3)~ ~=~ ~3~. Cuối cùng với ~i = 3~, ta có thể tính được ~a_4 = S(1, 3) \oplus S(1, 4) = 4~.

Với phần tử thứ ~p = 1~ và ~p = 2~, thông tin về nó là không đủ để xác định được giá trị của nó là bao nhiêu.

Subtask 1, 2, 3 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, ~3 \le n, m \le 10^3~.

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 ~S(l_i, r_i)~ ~=~ ~a_{l_i}~ ~\oplus~ ~a_{l_i+1}~ ~\oplus~ ... ~\oplus~ ~a_{r_i}~ là chính xác ~v_i~, với ~\oplus~ là phép toán thao tác bit XOR.

Input

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

Output

• In ra ~n~ dòng, dòng thứ ~p~ in ra giá trị của ~a_p~ và một số nguyên dương ~i~ trong đó giá trị của ~a_p~ chắc chắn xác định từ yêu cầu thứ ~i~ ~(1 \le i \le m)~. Trong trường hợp không thể, hãy in ra ~-1~ ~-1~.

Test

Input

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

Output

1 4
4 4
2 3
3 2
-1 -1

Note

Với yêu cầu thứ ~i = 1~, ta chỉ biết ~S(1, 4) = 4~ và không thể biết được điều gì. Đến với yêu cầu thứ ~i = 2~, ta có thể tính được ~a_4~ ~=~ ~S(1, 3)~ ~\oplus~ ~S(1, 4)~ ~=~ ~3~. Tiếp tục với ~i = 3~, ta có thể tính được ~a_3 = a_4\oplus S(3, 4) = 2~. Cuối cùng là với yêu cầu thứ ~i = 4~, ta có thể tính được ~a_2~ ~=~ ~a_3~ ~\oplus~ ~S(2, 3)~ ~=~ ~4~ và từ đó, ta có thể tính được thêm ~a_1 = a_2~ ~\oplus~ ~a_3~ ~\oplus~ ~S(1, 3) = 1~.

Với phần tử thứ ~p = 5~, thông tin về nó là không đủ để xác định được giá trị của nó là bao nhiêu.

Subtask 1, 2, 3 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 3, 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 ~S(l_i, r_i)~ ~=~ ~a_{l_i}~ ~\oplus~ ~a_{l_i+1}~ ~\oplus~ ... ~\oplus~ ~a_{r_i}~ là chính xác ~v_i~, với ~\oplus~ là phép toán thao tác bit XOR.

Input

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

Output

• In ra ~n~ dòng, dòng thứ ~p~ in ra giá trị của ~a_p~ và một số nguyên dương ~i~ trong đó giá trị của ~a_p~ chắc chắn xác định từ yêu cầu thứ ~i~ ~(1 \le i \le m)~. Trong trường hợp không thể, hãy in ra ~-1~ ~-1~.

Test

Input

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

Output

1 4
4 4
2 3
3 2
-1 -1

Note

Với yêu cầu thứ ~i = 1~, ta chỉ biết ~S(1, 4) = 4~ và không thể biết được điều gì. Đến với yêu cầu thứ ~i = 2~, ta có thể tính được ~a_4~ ~=~ ~S(1, 3)~ ~\oplus~ ~S(1, 4)~ ~=~ ~3~. Tiếp tục với ~i = 3~, ta có thể tính được ~a_3 = a_4\oplus S(3, 4) = 2~. Cuối cùng là với yêu cầu thứ ~i = 4~, ta có thể tính được ~a_2~ ~=~ ~a_3~ ~\oplus~ ~S(2, 3)~ ~=~ ~4~ và từ đó, ta có thể tính được thêm ~a_1 = a_2~ ~\oplus~ ~a_3~ ~\oplus~ ~S(1, 3) = 1~.

Với phần tử thứ ~p = 5~, thông tin về nó là không đủ để xác định được giá trị của nó là bao nhiêu.