Cho một số nguyên dương ~N~. Hãy tạo một hoán vị ~P_1, P_2, ..., P_N~ thỏa mãn: với mọi ~1 \le i \le n - 2~, ~P_i, P_{i + 1}, P_{i + 2}~ không phải độ dài ba cạnh của một tam giác.

Dữ liệu

• Dòng đầu tiên gồm một số nguyên dương ~T~ ~(1 \le T \le 100)~ - số lượng bộ dữ liệu bạn cần xử lý.
• ~T~ dòng tiếp theo, mỗi dòng gồm một số nguyên dương ~N~ ~(3 \le N \le 5000)~.

Kết quả

• Với mỗi bộ dữ liệu:
  • Nếu không tìm được hoán vị thỏa mãn, in ra ~-1~.
  • Ngược lại, in ra một dòng gồm ~N~ số nguyên dương là một hoán vị bất kỳ thỏa mãn.

Chấm điểm

Ví dụ

Dữ liệu

2
3
4

Kết quả

3 1 2
4 3 1 2

Alice cần tạo một mật khẩu mạnh cho tài khoản mạng xã hội của cô. Cô muốn viết một chương trình tự động, chương trình này nhận vào một xâu ký tự ~S~ chỉ gồm các số chữ cái trong bảng chữ cái tiếng Anh và trả ra một xâu ký tự ~P~ là mật khẩu được tạo. Xâu ~P~ được tạo từ xâu S theo quy tắc sau đây:

• Ký tự đầu tiên của xâu ~P~ là ký tự cuối cùng của xâu ~S~.
• Tiếp theo là tổng các ký tự số trong xâu ~S~.
• Tiếp theo là các ký tự số trong xâu ~S~ được sắp xếp theo thứ tự tăng dần.
• Tiếp theo là các ký tự chữ trong xâu ~S~ theo đúng thứ tự xuất hiện trong ~S~. Nếu ký tự là chữ hoa, chuyển sang chữ thường tương ứng.
• Cuối cùng là số lượng ký tự là chữ hoa trong xâu ~S~.

Bạn hãy giúp Alice viết chương trình để tạo mật khẩu như vậy nhé.

Dữ liệu

• Một dòng duy nhất gồm xâu ~S~ ban đầu có độ dài không quá ~10^5~ ký tự và chỉ gồm các ký tự chữ cái trong bảng chữ cái tiếng Anh và số.

Kết quả

• Một dòng duy nhất gồm xâu ~P~ được tạo ra

Chấm điểm

Ví dụ 1

Dữ liệu

icpc2025HCMC

Kết quả

C90225icpchcmc4

Giải thích

• Ký tự cuối cùng trong xâu ~S~ ban đầu là "C" .
• Xâu ~S~ có ~4~ ký tự số ~2,0,2,5~, sắp xếp lại là ~0,2,2,5~. Tổng giá trị của chúng là ~9~.
• Xâu ~S~ có ~4~ ký tự chữ cái in hoa là "H","C","M","C" , tương ứng với các chữ thường "h","c","m","c" .

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

Bạn cần phải tìm hai số nguyên ~X_0~ và ~V~, với ~0 \le X_0 \le M~ và ~-A \le V \le A~. Bạn được quyền yêu cầu máy chấm trả lời các câu hỏi. Với câu hỏi thứ ~i~, bạn có thể đưa ra một số nguyên ~Y~ và máy chấm sẽ trả lời:

• yes nếu ~X_0 + V \times i \le Y~.
• no nếu ngược lại.

Hãy tìm ra hai số nguyên này trong ít câu hỏi nhất có thể.

Tương tác

• Đầu tiên, chương trình của bạn nhập vào ba số nguyên không âm ~M, A, \theta~ ~(0 \le M, A \le 10^9, 1 \le \theta \le 4)~, với ~\theta~ là subtask.
• Tiếp theo, chương trình của bạn và máy chấm sẽ thay phiên nhau hỏi và trả lời như sau:
  • Để đặt câu hỏi, chương trình của bạn cần in ra một dòng theo định dạng ~?~ ~Y~ ~(-10^{18} \le Y \le 10^{18})~.
  • Máy chấm sẽ in ra yes hoặc no dựa trên giá trị ~Y~ của bạn.
• Sau khi có đủ thông tin, bạn in ra một dòng theo định dạng ~!~ ~X_0~ ~v~ ~(0 \le X_0 \le M, -10^9 \le V \le 10^9)~ để trả lời và kết thúc chương trình.

Lưu ý: bạn phải flush output sau khi in ra để máy chấm có thể đọc được. Trong C++, sử dụng lệnh cout << endl;. Trong Python, sử dụng lệnh sys.stdout.flush().

Chấm điểm

Với subtask 1, 2 và 3, chương trình của bạn có thể đặt ra tối đa ~31~ câu hỏi. Nếu sử dụng quá ~31~ câu hỏi, chương trình sẽ bị tính là Wrong answer.

Với subtask 4, chương trình của bạn có thể đặt ra không quá ~1000~ câu hỏi. Tuy nhiên, điểm của bạn cho mỗi test sẽ phụ thuộc vào số câu hỏi bạn đặt, gọi là ~X~ và được tính như sau:

• Nếu ~X \le 61~, điểm của bạn cho test đó là ~1~ điểm.
• Nếu ~61 < X \le 1000~, điểm của bạn cho test đó được tính theo công thức: ~P = 1 - 0.1 \times \log_2(X - 60)~
• Nếu ~X > 1000~, điểm của bạn cho test đó là ~0~ điểm.

Ví dụ

Đếm số lượng dãy số nguyên ~a_1, a_2, ..., a_N~ thỏa mãn:

• ~a_1 < a_2 < ... < a_N~
• ~L_i \le a_i \le R_i~ với mọi ~i~.

Dữ liệu

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(1 \le N \le 200)~.
• ~N~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~L_i, R_i~ ~(1 \le L_i \le R_i \le 10^9)~.

Kết quả

• Một dòng duy nhất là số lượng dãy số tìm được. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư của nó khi chia cho ~10^9 + 7~.

Chấm điểm

Ví dụ

Dữ liệu

3
1 4
3 3
2 5

Kết quả

4

Giải thích

• Có 4 dãy thỏa mãn là: ~(1, 3, 4), (2, 3, 4), (1, 3, 5), (2, 3, 5)~.

Bạn được cho hai số nguyên ~N, D~. Bạn cần xây dựng một bảng ~N \times N~ thỏa mãn các điều kiện sau:

• Các số trên bảng có giá trị trong đoạn ~[1, 10^6]~.
• Tổng các số trên cùng một hàng và một cột là một số nguyên tố.
• Nếu ~D = 1~, tổng các số trên hai đường chéo chính và phụ cũng là một số nguyên tố.

Dữ liệu

• Một dòng duy nhất gồm hai số nguyên ~N, D~ ~(1 \le N \le 1000, 0 \le D \le 1)~.

Kết quả

• Nếu không tồn tại bảng thỏa mãn, in ra ~-1~.
• Ngược lại, in ra bảng tìm được trên ~N~ dòng. Nếu có nhiều bảng thỏa mãn, in ra một bảng bất kỳ.

Chấm điểm

Ví dụ 1

Dữ liệu

2 0

Kết quả

1 2
4 3

Giải thích

• Tổng các số trên các hàng lần lượt là ~3~ và ~7~; tổng các số trên các cột lần lượt là ~5~ và ~5~. Tất cả các tổng đều là các số nguyên tố. Do ~D = 0~ nên chúng ta không cần quan tâm đến các đường chéo.

Ví dụ 2

Dữ liệu

3 1

Kết quả

1 1 5
1 3 3
3 1 3

Cho dãy số nguyên dương ~n~ phần tử ~a_1, a_2, ..., a_n~. Nhiệm vụ của bạn là đếm số lượng đoạn con liên tiếp ~a[l...r]~ sao cho ~1 \le l \le r \le n~ và số lần xuất hiện của các phần tử trong dãy phải nhiều hơn ~1~.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 2 \times 10^5)~.
• Dòng thứ hai chữa dãy số nguyên ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le n)~.

Kết quả

• In ra số dãy con liên tiếp thoả mãn yêu cầu đề bài.

Chấm điểm

Ví dụ 1

Dữ liệu

4
1 2 2 1

Kết quả

2

Giải thích

• Có 2 đoạn con thoả mãn, gồm: ~[2, 3]~, ~[1, 4]~

Ví dụ 2

Dữ liệu

5
3 6 3 3 3

Kết quả

3