Alice có ~n~ viên sỏi. Cô ta muốn chơi với Bob một trò chơi như sau:

• Đầu tiên, Bob phải chia ~n~ viên sỏi thành ~m~ đống, sao cho mỗi đống có ít nhất một viên sỏi.
• Hai người sẽ chơi một trò chơi và Alice là người đi trước.
  • Đến lượt của mình, mỗi người sẽ chọn một đống sỏi (còn ít nhất một viên), và lây ra một số viên sỏi từ đống sỏi đó (có thể lấy hết nhưng không thể không lấy viên nào).
  • Ai không thể thực hiện được lượt chơi của mình thì thua cuộc. Hãy giúp Bob tìm một cách chia các viên sỏi sao cho anh ta luôn thắng nếu chơi tối ưu sau đó.

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 hai số nguyên dương ~n, m~ ~(1 \le n \le 10^9, 1 \le m \le 10^5, n \ge m)~.
• Dữ liệu đầu vào đảm bảo tổng các giá trị ~m~ trong các bộ dữ liệu không vượt quá ~2 \times 10^5~.

Kết quả

• Với mỗi bộ dữ liệu:
  • In ra NO nếu không có cách nào để Bob đảm bảo chiến thắng.
  • In ra YES nếu có cách để Bob đảm bảo chiến thắng. Tiếp theo in ra ~m~ số nguyên dương ~a_1, a_2, ..., a_m~ với ~a_i~ là số viên sỏi ở đống thứ ~i~.

Ví dụ

Dữ liệu

3
3 1
4 2
5 5

Kết quả

NO
YES 2 2
NO

Giải thích

• Ở bộ dữ liệu đầu tiên, cách chia duy nhất là đặt cả ~3~ viên vào một đống sỏi. Alice chỉ cần lấy hết ~3~ viên sỏi trong lượt đi đầu tiên để đảm bảo chiến thắng.
• Ở bộ dữ liệu thứ hai, nếu Bob chia các viên sỏi thành hai nhóm, mỗi nhóm có ~2~ viên sỏi, anh ta luôn có chiến thuật lặp lại nước đi của Alice trên đống sỏi còn lại (ví dụ: nếu Alice bốc ~1~ viên sỏi ở đống ~1~ thì Bob bốc ~1~ viên sỏi ở đống ~2~ và ngược lại) để đảm bảo chiến thắng.
• Ỏ bộ dữ liệu thứ ba, cách chia duy nhất là chia ~5~ viên sỏi vào ~5~ đống khác nhau. Dễ thấy với cách chia này Bob không thể giành chiến thắng.

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~.

Đây là bài toán tương tác với máy chấm

Alice có ~n~ lá bài được xếp thành một chồng, trong đó có một lá bài đặc biệt được xếp ở vị trí thứ ~k~ từ trên xuống. Cô và Bob sẽ chơi một trò chơi như sau, với Alice là người đi trước:

• Mỗi lượt, người chơi bốc không quá ~r~ lá bài ở đầu hoặc cuối lá bài.
• Người bốc được là bài đặc biệt là người chiến thắng.

Bạn được biết các giá trị ~n, k, r~, hãy xác định xem ai sẽ là người chiến thắng nếu cả hai chơi tối ưu. Sau đó, hãy đóng vai người chơi đó và thực hiện chơi trò chơi với máy chấm. Bạn phải chơi ~T~ ván với máy chấm trong mỗi testcase.

Tương tác

• Đầu tiên, chương trình của bạn cần nhập vào một số nguyên dương ~T~ là số ván bạn cần chơi với máy ~(1 \le T \le 10)~.
• Các ván chơi có tương tác như sau:
  • Đầu tiên, chương trình của bạn cần nhập vào bốn số nguyên dương ~n, k, r~ ~(1 \le k, r \le n \le 10^5)~.
  • Chương trình của bạn cần in ra Alice hoặc Bob tương ứng với nhân vật bạn muốn đóng vai.
  • Sau đó, trò chơi bắt đầu. Hai bên thay phiên nhau thực hiện lượt chơi như sau:
    • Nếu là lượt của bạn, in ra:
      • ~1\ x~ nếu bạn muốn bốc ~x~ lá ở phần đầu bộ bài.
      • ~2\ x~ nếu bạn muốn bốc ~x~ lá ở phần cuối bộ bài.
    • Nếu là lượt chơi của máy, đọc nước đi của máy theo định dạng tương tự.
  • Chương trình của bạn cần tự xác định ván đấu đã kết thúc hay chưa. Khi ván đấu kết thúc chương trình của bạn cần ngay lập tức chuyển sang ván mới hoặc kết thúc chương trình trong trường hợp đã chơi đủ ~T~ ván hoặc bạn thua.

Ví dụ

Tương tác

Alice vừa được học về ước và bội của một số nguyên trên lớp. Nếu một số nguyên ~a~ chia hết cho một số nguyên ~b~, ta nói rằng ~a~ là bội của ~b~ và ~b~ là ước của ~a~.

Để kiểm tra kiến thức và khả năng tính toán của các học sinh, thầy giáo của Alice đã giao cho các bạn một dãy số ~a_1, a_2, ..., a_n~ rất dài và yêu cầu các bạn chọn ra càng nhiều phần tử càng tốt sao cho khi ghép chúng lại thành một dãy với thứ tự các số được giữ nguyên như trong dãy ~a~ ban đầu, ký hiệu là dãy ~b_1, b_2, ..., b_k~, thì ~b_i~ là ước hoặc bội của ~b_{i - 1}~ với mọi số nguyên ~2 \le i \le k~. Bạn nào chọn được nhiều phần tử nhất (giá trị ~k~ lớn nhất) sẽ nhận được một phần thưởng từ thầy giáo.

Alice rất muốn chiến thắng trong trò chơi này. Hãy giúp Alice tìm ra dãy ~b~ dài nhất.

Dữ liệu

• 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 dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^5)~.

Kết quả

• Dòng đầu tiên gồm một số nguyên dương ~k~ - độ dài dãy ~b~ lớn nhất bạn tìm được.
• Dòng tiếp theo gồm ~n~ số nguyên ~x_1, x_2, ..., x_k~, với ~x_1 < x_2 < ... < x_k~ là vị trí của các phần tử của dãy ~b~ trong dãy ~a~ ban đầu, hay nói cách khác, ~b_i = a_{x_i}~. Nếu có nhiều kết quả, in ra kết quả bất kỳ.

Ví dụ

Dữ liệu

5
1 2 3 4 5

Kết quả

3
1 2 4

Giải thích

• Ta có ~b = (a_1, a_2, a_4) = (1, 2, 4)~, với ~2~ là bội của ~1~ và ~4~ là bội của ~2~. Dễ dàng nhận thấy đây là dãy ~b~ dài nhất thỏa mãn.

Chắc hẳn các bạn đã quen với mật mã Caesar, một trong những kỹ thuật mã hóa đơn giản và phổ biến nhất. Với kỹ thuật mã hóa này, mỗi ký tự trong bạch văn (văn bản ban đầu) sẽ được thay thế bởi một ký tự khác, có vị trí cách nó một khoảng xác định k trong bảng chữ cái. Ví dụ, với ~k = 3~, ký tự a sẽ được thay bằng d, b thay bằng e, c thay bằng f, …, y thay bằng b, z thay bằng c.

Tuy phổ biến, nhưng đây là một kỹ thuật rất dễ bị phá giải. Để cải tiến kỹ thuật này, Alice có một sáng kiến như sau: nối bạch văn và văn bản đã mã hóa vào cùng một chuỗi, thêm một số ký tự gây nhiễu vào trước phần bạch văn, giữa hai văn bản, hoặc sau phần văn bản đã mã hóa để tạo thành một chuỗi mới rồi gửi cho những người bạn của côy. Ví dụ, từ bạch văn abc, với ~k = 3~, cô có thể mã hóa thành def, sau đó chèn thêm một số ký tự gây nhiễu để tạo thành xâu xabcyzdeft.

Bạn được cho một xâu ~s~ là xâu cuối cùng thu được sau quá trình mã hóa. Hãy tìm độ dài lớn nhất có thể của bạch văn.

Dữ liệu

• Một dòng duy nhất gồm xâu ~s~ có độ dài không quá ~2 \times 10^5~.

Kết quả

• Một dòng duy nhất là độ dài lớn nhất của bạch văn.

Ví dụ

Dữ liệu

sqrtonlinejudge

Kết quả

2

Giải thích

Bạch văn dài nhất có thể là sq, được mã hóa theo mật mã Caesar thành nl với ~k = 21~.

Trên một mặt hồ có rất nhiều lá sen xếp thành một hàng dài. Một ngày chủ nhật, Alice mang theo một vài con ếch ra bờ hồ để nghiên cứu cách nhảy của chúng trên những chiếc lá.

Alice đánh số các lá theo thứ tự tăng dần từ trái sang phải. Cô ta dự định thực hiện buổi thí nghiệm trong ~q~ phút. Mỗi phút Alice sẽ thực hiện một trong hai hành động sau:

• Thả một con ếch có bước nhảy bằng ~k~ vào chiếc lá thứ ~i~. Mỗi phút con ếch này sẽ nhảy về bên phải ~k~ lá. Hay nói cách khác, nếu ở phút thứ ~t~ con ếch đang ở chiếc lá thứ ~x~ thì ở phút thứ ~t + 1~ nó sẽ nhảy sang chiếc lá thứ ~x + k~.
• Đếm số con ếch đang ở trên các lá ~l, l + 1, ..., r~.

Do biết trước bước nhảy của những con ếch, Alice muốn tính toán trước kết quả của các hành động đếm để có thể đối chiếu với kết quả thực tế. Các bạn hãy giúp Alice thực hiện việc này nhé.

Dữ liệu

• Dòng đầu tiên gồm một số nguyên dương ~q~ ~(1 \le q \le 10^5)~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ mô tả hành động của Alice ở phút thứ ~i~ và thuộc một trong hai dạng sau:
  • ~1\ k\ i~: thả một con ếch có bước nhảy ~k~ ở chiếc lá ~i~ ~(1 \le i, k \le 10^5)~.
  • ~2\ l\ r~: đếm số con ếch trên những chiếc lá thuộc đoạn ~[l, r]~ ~(1 \le l \le r \le 10^5)~.

Kết quả

• In ra các số nguyên không âm là câu trả lời cho các hành động loại 2, mỗi câu trả lời in trên một dòng.

Ví dụ

Dữ liệu

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

Kết quả

2
1

Giải thích

Dưới đây là bảng cho biết vị trí của mỗi con ếch ở từng thời điểm.

Alice có rắt nhiều bạn. Hôm nay, mỗi người trong số những người bạn của Alice đưa cho cô ấy một xâu ký tự. Biết rằng tất cả các xâu đều có độ dài bằng nhau. Alice muốn sắp xếp và ghép các xâu theo một thứ tự nào đó, sao cho xâu thu được có thứ tự từ điển nhỏ nhất. Các bạn hãy giúp Alice thực hiện công việc này nhé.

Nhắc lại: Xâu ~a~ được coi là có thứ tự từ điển nhỏ hơn xâu ~b~ khi và chỉ khi tồn tại một vị trí ~x~ sao cho:

• ~a_i = b_i~ với mọi ~1 < i < x~.
• ~a_x < b_x~.

Dữ liệu

• Gồm nhiều dòng, mỗi dòng gồm một xâu mà những người bạn đưa cho Alice. Tổng độ dài của các xâu không vượt quá ~10^5~.

Kết quả

• Một dòng duy nhất là xâu có thứ tự từ điển nhỏ nhất thu được.

Ví dụ

Dữ liệu

ab
bc
ac

Kết quả

abacbc

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

Chú ý giới hạn thời gian (và bộ nhớ) bất thường cho bài này

Xét biểu thức sau:

$$\pm 1^k \pm 2^k \pm 3^k \pm ... \pm m^k = n$$

Một thầy giáo dạy toán đã chứng minh được rằng: Với mọi cặp số nguyên dương ~(n, k)~, luôn tồn tại một số nguyên dương ~m~ và một cách thay thế các dấu ~\pm~ thành dấu cộng hoặc trừ để biểu thức đúng. Ví dụ, với ~(n, k)~ = ~(7, 3)~, ta có ~-1^3 + 2^3 = 7~. Thầy giáo nhận thấy bài toán này cũng khá hay, do đó thầy muốn biến bài toán này thành một bài kiểm tra cho các học sinh của mình. Cụ thể, thầy sẽ đưa cho mỗi bạn học sinh một cặp số nguyên dương ~(n, k)~. Mỗi bạn sẽ phải tìm một giá trị ~m~ và một cách chọn dấu thỏa mãn với cặp số mà mình được giao.

Bạn hãy thử giải quyết các câu hỏi của thầy giáo nhé.

Dữ liệu

• Dòng đầu tiên gồm một số nguyên dương ~T~ ~(1 \le T \le 100)~ là số câu hỏi của thầy giáo.
• ~T~ dòng tiếp theo, mỗi dòng gồm hai số nguyên không âm ~n, k~ ~(0 \le n \le 10^{min (10, 2k)}, 1 \le k \le 7)~.

Kết quả

• Với mỗi câu hỏi, in ra một xâu chỉ gồm các dấu + hoặc - mô tả cách điền dấu thỏa mãn.

Ví dụ

Dữ liệu

2
0 2
7 3

Kết quả

++-+--+
-+

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

Alice muốn gửi cho Bob một con số bí mật. Tuy nhiên, việc gửi theo cách thông thường rất dễ bị tin tặc tấn công. Tình cờ thay, hôm nay Alice được biết đến dãy số Fibonacci được định nghĩa như sau:

• ~f_n = 1~ với ~1 \le n \le 2~.
• ~f_n = f_{n-1}+f_{n-2}~ với ~n > 2~.

Với ý tưởng từ dãy Fibonacci, Alice đã tạo ra một dãy ~m~ như sau:

• ~m_1 = a, m_2 = b, m_3 = c~.
• ~m_n = m_{n-1} \oplus m_{n-2} \oplus m_{n-3}~ với ~n > 3~, với ~\oplus~ là phép toán thao tác bit XOR.

Con số của Alice gửi cho Bob sẽ là giá trị ~m_l + m_{l + 1} + ... + m_r~. Alice sẽ gửi cho Bob bộ năm số ~(a, b, c, l, r)~. Bạn hãy giúp Bob tìm ra con số mà Alice muốn gửi nhé.

Dữ liệu

• ~5~ số nguyên dương ~a, b, c, l, r~ ~(1 \le a, b, c, l, r \le 10^{12}; l \le r)~.

Kết quả

• In ra phần dư của con số bạn tìm được khi chia cho ~1234567891~.

Ví dụ

Dữ liệu

1 2 3 4 5

Kết quả

1

Giải thích

• Dựa vào quy luật của dãy số, dễ dàng tính ~m_4 = 0, m_5 = 1~. Từ đó ta có con số mà Alice muốn gửi là ~m_4 + m_5 = 1~.

Alice có ~n~ chiếc đèn, mỗi chiếc đèn có 3 màu: đỏ, vàng hoặc xanh. Ban đầu, các đèn đang có các màu lần lượt là ~a_1, a_2, ..., a_n~, với ~a_i = 0~ nếu đèn thư ~i~ có màu xanh, ~a_i = 1~ nếu đèn thứ ~i~ có màu vàng, ~a_i = 2~ nếu đèn thứ ~i~ có màu đỏ. Các đèn được nối với nhau thành một dãy. Có ~n~ nút bấm, nút bấm thứ ~i~ chuyển đổi trạng thái các đèn có vị trí từ ~1~ đến ~i~: đèn xanh chuyển sang đèn vàng, đèn vàng chuyển sang đèn đỏ, đèn đỏ chuyển sang đèn xanh.

Alice muốn biết cô ta cần phải ấn các nút bấm bao nhiêu lần để toàn bộ dãy đèn trở thành màu xanh. Tuy nhiên cô nhận thấy bài toán này vẫn còn quá dễ nên cô muốn biến nó thành một bài toán khó hơn. Cụ thể, Alice sẽ thực hiện thay đổi trạng thái các đèn ~q~ lần. Mỗi lần, Alice sẽ chọn ra ba số nguyên dương ~l, r, k~. Alice sẽ thực hiện thay đổi trạng thái đèn thứ ~l~ ~1^k~ lần, đèn thứ ~l + 1~ ~2^k~ lần, ..., đèn thứ ~r~ ~(r - l + 1)^k~ lần. Sau mỗi lần thay đổi, Alice muốn biết cô ta cần phải ấn nút tối thiểu bao nhiêu lần để toàn bộ dãy đèn trở thành màu xanh.

Dữ liệu

• 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~ ~(0 \le a_i \le 2)~.
• ~q~ dòng tiếp theo, mỗi dòng gồm ba số nguyên dương ~l, r, k~ ~(1 \le l \le r \le n, 0 \le k \le 10^9)~.

Kết quả

Gồm ~q + 1~ dòng:

• Dòng đầu tiên gồm một số nguyên dương là số lần ấn nút tối thiẻu đẻ toàn bộ dãy đèn trở thành màu xanh trong trạng thái đèn đầu tiên.
• ~q~ dòng tiếp theo, dòng thứ ~i~ gồm một số nguyên dương là số lần ấn nút tối thiẻu đẻ toàn bộ dãy đèn trở thành màu xanh trong trạng thái đèn sau lần thay đổi thứ ~i~.

Ví dụ

Dữ liệu

5 2
0 1 1 2 2
4 5 1
1 1 2

Kết quả

3
6
5

Giải thích

• Trong trạng thái đèn đầu tiên, cần ấn các nút ~1, 3, 5~ mỗi nút một lần để các đèn được biến đổi: ~(0, 1, 1, 2, 2) \rightarrow~ ~(1, 1, 1, 2, 2) \rightarrow~ ~(2, 2, 2, 2, 2)~ ~\rightarrow (0, 0, 0, 0, 0)~.
• Sau lần thay đổi đầu tiên, dãy đèn trở thành ~(0, 1, 1, 0, 1)~. Cần ấn nút ~1~ 1 lần, nút ~3~ 2 lần, nút ~4~ 1 lần, nút ~5~ 2 lần.
• Sau lần thay đổi thứ hai, dãy đèn trở thành ~(1, 1, 1, 0, 1)~. Ấn các nút tương tự như trên, trừ nút ~1~.