lqdoj010

Cho \(A\) là một số nguyên dương bất kì, gọi \(Rev(A)\) là số đảo ngược của \(A\). \(A\) được gọi là số lẻ loi nếu các chữ số của \(A+Rev(A)\) đều là số lẻ. Lưu ý rằng \(Rev(A)\) không được bắt đầu bằng số \(0\). Nếu \(Rev(A)\) bắt đầu bằng số \(0\) thì \(A\) không được coi là số lẻ loi.

Hãy kiểm tra xem số nguyên dương \(A\) được cho có phải số lẻ loi hay không? Nếu có hãy in ra YES, ngược lại hãy in NO.

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(t\) \((1 \leq t \leq 10)\) - Số lượng testcase.
• Cấu trúc của mỗi test case:
• Dòng thứ nhất của mỗi case chứa 1 số nguyên dương \(n\), số lượng các số cần kiểm trong test case này
• \(n\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(a_i\) \((1 \leq a_i \leq 10^{18}\))

Output

• Ứng với mỗi \(a_i\), in ra YES nếu số đó là lẻ loi. Ngược lại in ra NO.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \leq n \leq 10^5\)
• Subtask \(2\) (\(70\%\) số điểm): \(10^5+1 \leq n \leq 10^{18}\)

Example

2
5
36
63
12
21
5
3
12
21
9 

YES
YES
YES
YES
NO
YES
YES
NO

Đây là một version khác của bài Số lẻ loi 1.

Cho \(A\) là một số nguyên dương bất kì, gọi \(Rev(A)\) là số đảo ngược của \(A\). \(A\) được gọi là số lẻ loi nếu các chữ số của \(A+Rev(A)\) đều là số lẻ. Lưu ý rằng \(Rev(A)\) không được bắt đầu bằng số \(0\). Nếu \(Rev(A)\) bắt đầu bằng số \(0\) thì \(A\) không được coi là số lẻ loi.

Đề bài: Cho số nguyên dương \(n\). In ra số lẻ loi bất kì có số chữ số đúng bằng \(n\).

Input

• Một dòng duy nhất chứa số nguyên dương \(n \ (1 \leq n \leq 18)\).

Output

• In ra số lẻ loi bất kì có số chữ số đúng bằng \(n\). Nếu không có số nào thỏa mãn, in ra \(-1\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \leq n \leq 6\).
• Subtask \(2\) (\(70\%\) số điểm): \(7 \leq n \leq 18\).

Example

1 

-1

2 

36

Giả sử ta có một chuỗi ngoặc đơn đúng, ta gọi chuỗi này là \(S\), khi đó \(S\) có hai cách giải mã sau đây:

• Cách 1: \(S\) sẽ được mã hóa dưới dạng \(P=p_1,p_2,...,p_n\). Trong đó \(p_i\) là số lượng ngoặc đơn trái "(" đứng trước ngoặc đơn phải ")" thứ \(i\) tính từ trái.

• Cách 2: \(S\) sẽ được mã hóa dưới dạng \(W=w_1,w_2,...,w_n\). Gọi \(r\) là vị trí dấu ngoặc đơn ")" thứ \(i\) tính từ trái sang. Gọi \(l\) là vị trí của dấu ngoặc đơn trái "(" tương thích với dấu ngoặc ")" đó. Khi đó \(w_i\) chính bằng số lượng dấu ngoặc đơn phải ")" nằm trong đoạn từ \(l\) tới \(r\).

• Ví dụ: Ta có chuỗi \(S=(((()()())))\). Khi đó ta có dãy \(P\) tương ứng là: \(P=4,5,6,6,6,6\) và dãy \(W\) tương ứng là \(W=1,1,1,4,5,6\). \(W[1] = 1\) vì dấu ngoặc đơn ")" thứ nhất nằm ở vị trí \(5\) tương ứng với dấu ngoặc "(" nằm ở vị trí \(4\). Trong đoạn \(4\) tới \(5\) của \(S\) có \(1\) dấu ngoặc đơn ")".

Yêu cầu: Cho dãy \(P\) bất kì, tìm dãy \(W\) tương ứng.

Input

• Dòng thứ nhất chứa chứa số nguyên dương \(n \ (1 \leq n \leq 10^5)\) - Là độ dài của dãy \(P\).

• Dòng thứ hai chứa \(n\) số nguyên dương \(p_i \ (1 \leq p_i \leq n)\) - Mỗi số cách nhau bởi dấu cách.

Output

• Nếu không tồn tại dãy \(W\) thỏa mãn yêu cầu bài toán, in ra \(-1\). Ngược lại, in ra dãy \(W\) cần tìm.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n\leq 10\)..
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 100\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 5000\).
• Subtask \(4\) (\(40\%\) số điểm): \(n \leq 10^5\).

Example

3
2 2 3 

1 2 1

Đây là bài toán interactive.

Các bạn có thể tìm hiểu về dạng này này tại đây.

ami có một số \(n, n\leq10000\). Các bạn sẽ không biết số này. Các bạn cần đoán số này dùng không quá 30 thao tác sau:

• Các bạn có thể hỏi ami một dãy số \(A\) gồm \(k\) phần tử nguyên dương \((k\leq5000)\). ami sẽ trả về một số bất kì \(A_i\) trong dãy số mà \(n\) chia hết cho \(A_i\) (\(n \% A_i = 0\)).

Để hỏi ami, các bạn cần in ra câu hỏi có dạng sau :

• \(?\space n \space A_1 \space A_2 \space A_3 ... A_n\).

Ví dụ, để hỏi dãy có \(4\) phần tử là \(1\space2\space 3\space 4\), các bạn cần in ra "? 4 1 2 3 4" (dấu ngoặc kép chỉ để nhấn mạnh).

Đương nhiên, sau khi in ra câu hỏi, các bạn cần phải xuống dòng và flush câu hỏi này. Sau đó ami sẽ trả lời lại các bạn, câu trả lời có dạng sau :

• \(x\).

Nếu \(x = −1\), điều này có nghĩa rằng câu hỏi mà các bạn hỏi là không hợp lệ. Các bạn cần dừng chương trình ngay và nhận kết quả là "Wrong answer". Nếu chương trình không dừng lại, các bạn sẽ nhận được một thông báo bất kì, vì các bạn đang tương tác với ami đã đi gánh team.

Nếu \(x = 0\), điều này có nghĩa rằng, không tồn tại \(x\) mà \(n\) chia hết \(A_x\).

Nếu \(x\gt0\), ami sẽ đảm bảo rằng \(n\) chia hết \(A_x\).

Sau khi các bạn đã đoán ra số n, các bạn cần thông báo cho ami. Thông báo như sau :

• ! n.

Ví dụ, số các bạn đoán là \(69\), các bạn cần thông báo "! 69" (dấu ngoặc kép chỉ để nhấn mạnh).

Example

1
2
4
3
0 

? 4 4 2 3 1
? 4 1 2 3 4
? 4 1 2 3 4
? 4 1 2 3 4
? 4 69 96 69 96
! 12

Cho số nguyên dương \(n\). Đếm xem có bao nhiêu nhiêu dãy \(A\) thỏa mãn:

• \(A\) không giảm.
• \(A\) có \(n\) phần tử, được đánh chỉ số từ \(1\).
• \(A[n]=n\) và \(A[i] \ge i \ \forall i=\overline{1,n}\).

Vì đáp số có thể lớn, nên kết quả in ra sẽ lấy theo \(mod \ 10^9 + 7\).

Input

• Dòng duy nhất chứa số nguyên dương \(n \ (1 \leq n \leq 10^6)\).

Output

• In ra kết quả đã lấy \(mod \ 10^9 + 7\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 10\).
• Subtask \(2\) (\(70\%\) số điểm): \(n\leq 300\).
• Subtask \(1\) (\(30\%\) số điểm): \(n\leq 3000\).
• Subtask \(2\) (\(70\%\) số điểm): \(n \leq 10^6\).

Example

2 

2

Cho mảng \(A\) gồm \(n\) phần tử và các phần tử được sắp xếp tăng dần từ \(1\) đến \(n\) (Tức là \(A[]=\left\{1,2,3,...,n\right\}\)). Nhiệm vụ của bạn là in ra số tập lệnh tối thiểu để chuyển mảng \(A\) thành mảng gồm các phần tử được sắp xếp theo thứ tự giảm dần (Tức là, sau khi biến đổi: \(A[]=\left\{n,n-1,n-2,...,1\right\}\))

Mảng \(A\) được đánh chỉ số bắt đầu từ \(1\).

Mỗi tập lệnh có cấu trúc như sau: \((p_1,len,p_2)\). Điều kiện \(1\) \(\leq\) \(p_1\) ; \(1\) \(\leq\) \(len \leq\) \(n+1 - p_1\) ; \(0\) \(\leq\) \(p_2\) \(\leq\) \(n\) \(-\) \(len\)

Ta áp dụng các tập lệnh đó vào \(A\) như sau: Lấy subarray (có nghĩa là mảng con gồm các phần tử liên tiếp) từ vị trí \(p_1\) đến \(p_1+len-1\), sau đó xóa chúng đi và thêm lại vào phía sau vị trí \(p_2\). Nếu \(p_2=0\), thì ta hiểu subarray đó được thêm vào phía trước đầu tiên của mảng \(A[]\).

Ví dụ: Giả sử ta có mảng \(A[]=1,2,3\), áp dụng tập lệnh \((1,1,2)\) vào \(A\), ta có quá trình biến đổi như sau:

• Ta tìm được \(subarray[]=1\).

• Xóa đi subarray này, thì mảng \(A\) còn lại: \(A[]=2,3\)

• Thêm subarray này lại vào vị trí sau vị trí thứ \(2\), ta được \(A[]=2,3,1\).

Hoặc giả sử ta áp dụng tập lệnh \((2,2,0)\). Khi đó \(A[]\) sẽ trở thành \(A[]=2,3,1\).

Yêu cầu: Cho số nguyên dương \(n\). In ra số tập lệnh tối thiểu cần dùng, và liệt kê chúng ra. Nếu có nhiều đáp án, in ra bất kì.

Input

• Nhập số \(n(1\leq n\leq 1000)\).

Output

• Dòng thứ nhất chứa số tập lệnh tối thiểu cần dùng.

• In ra các dòng liệt kê số tập lệnh trên, mỗi tập lệnh một dòng.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1\leq n \leq 100\).
• Subtask \(2\) (\(70\%\) số điểm): \(101\leq n \leq 1000\).

Example

3 

2
1 1 2
1 1 1