Cho một xâu con độ dài \(n\). Hãy tìm cách thay thế nhiều nhất 2 kí tự để thu được 1 xâu đối xứng.

Input

Gồm \(T\) testcase \((T \leq 10)\), mỗi testcase nằm trên một dòng:

• Mỗi dòng gồm 1 xâu \(s\) \((|s| \leq 600)\)

Output

• Hãy in ra \(T\) dòng, mỗi dòng là YES nếu có cách thực hiện yêu cầu trên, hoặc NO nếu không tồn tại cách nào.

Example

zcxxxc
xxczxx
zxcvbn 

YES
YES
NO

Note

Cách biến đổi từng testcase như sau:

• zcxxxc \(\rightarrow\) ccxxcc
• xxczxx \(\rightarrow\) xxccxx
• Không có cách biến đổi thỏa mãn.

Cách đọc input bằng Python:

import sys
for s in sys.stdin:
    # xử lý s

Vào một buổi sáng, rất tình cờ Nam nhìn thấy một số nguyên dương \(N\) trên đường từ nhà đến trường. Vì Nam rất thích số \(30\) nên Nam muốn biến đổi số \(N\) thành số \(M\) có dạng là số lớn nhất và là bội của số \(30\) bằng cách thay đổi vị trí của các chữ số trong số \(N\) mà Nam nhìn thấy.

Bạn hãy hỗ trợ Nam bằng cách viết chương trình để tìm số \(M\) (nếu nó tồn tại).

Input

• Gồm một dòng duy nhất chứa số nguyên \(N\) (\(N\) có tối đa là \(10^5\) chữ số).

Output

• In ra số \(M\) tìm được. Nếu không tồn tại \(M\) thì in ra \(-1\).

Example

30 

30

102

210

3333333333333333333333333333 

-1

Cho dãy \(a\) gồm \(n\) số nguyên, bạn phải đặt giữa \(n\) số nguyên này \(2\) phép nhân và \(n-3\) phép cộng sao cho kết quả biểu thức là lớn nhất.

Ví dụ: với \(n=5\) và dãy \(a_i\) là \(4,7, 1, 5, 3\) thì bạn có thể có các biểu thức:

• \(4 + 7 \cdot 1 + 5 \cdot 3\)
• \(4 \cdot 7 +1 + 5 \cdot 3\)

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(4 \leq n \leq 10^3\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(a_i\) (\(1 \leq a_i \leq 10^4\)).

Output

• Ghi một số nguyên dương duy nhất là giá trị lớn nhất của biểu thức thu được.

Example

5
4
7
1
5
3

44

Cho một dãy gồm \(n\) số nguyên \(A=(a_1,a_2,…,a_n)\). Ta định nghĩa: đoạn con của dãy \(A\) là một dãy các phần tử liên tiếp nhau thuộc \(A\). Hoặc có thể viết \((a_i,a_{i+1},…,a_j)\) là một đoạn con của \(A\) với \(i \leq j\). Độ dài của đoạn con được tính là số phần tử của đoạn con đó, ví dụ, đoạn con trên có độ dài là \(j-i+1\).

Yêu cầu: Tìm một đoạn con có độ dài ngắn nhất chứa cả số lớn nhất và số nhỏ nhất của dãy \(A\).

Input

• Dòng đầu chứa số nguyên dương \(n \ (1 \leq n \leq 10^5)\).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1,a_2,….,a_n\).

Output

• Một số duy nhất là độ dài của đoạn con tìm được thỏa mãn yêu cầu đề bài.

Example

8
1 3 6 2 8 1 3 8 

2

Cấp số nhân là một dãy số thỏa mãn điều kiện tỷ số giữa \(2\) phần tử liên tiếp là hằng số. Xét dãy cấp số nhân \(1,x,x^2,x^3,….,x^n\).

Yêu cầu: Cho 2 số nguyên \(x\) và \(n\). Tính tổng tất cả các phần tử trong cấp số nhân đã cho. Vì kết quả có thể rất lớn nên chỉ đưa ra số dư trong phép chia cho \(m\).

Input

• Một dòng chứa 3 số nguyên dương \(x,n,m \ (x \leq 100, n \leq 10^{18}, m \leq 10^7)\).

Output

• Một số nguyên là kết quả của bài toán.

Example

2 6 1000 

127

Cho một dãy số nguyên \(a_1, a_2, a_3, …, a_n\) và một số nguyên \(k\). Một dãy con \(1 \leq i \leq j \leq n\) được gọi là hoàn hảo nếu như \(a_i + a_{i + 1} + a_{i + 2} + … + a_j = k\).

Yêu cầu: Hãy đếm xem có bao nhiêu dãy con hoàn hảo từ dãy đã cho.

Input

• Dòng đầu tiên chứa số \(n \ (n \leq 10^5)\) và \(k \ (|k| \leq 10^4)\) cách nhau bởi dấu cách.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_i \ (|a_i| \leq 10^4)\).

Output

• Một số duy nhất là kết quả tìm được.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 5000\).
• Subtask \(3\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 5
1 2 3 4 5 

2