Cho dãy số \(A\) gồm \(N\) phần tử \(a_1,a_2,...,a_N\). Đếm số lượng số âm, số dương trong dãy số.

Input

• Dòng đầu tiên gồm số nguyên dương \(N\) \((N \le 10^5)\);
• Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,..,a_N\) \((|a_i| \le 10^9)\)

Output

• In ra số lượng số âm, số lượng số dương.

Example

5
-2 4 0 5 4 

1 3

Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,...,a_N\). Với mỗi chỉ số \(1 \le i \le N\) đếm xem có bao nhiêu phần tử bé hơn \(a_i\).

Input

• Dòng đầu tiên gồm số nguyên dương \(N\) \((2 \le N \le 10^5)\)
• Dòng thứ hai gồm \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^9)\)

Output

• In ra \(N\) số nguyên, số thứ \(i\) cho biết số phần tử nhỏ hơn \(a_i\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 10^3\)
• Subtask \(2\) (\(50\%\) số điểm): không ràng buộc gì thêm.

Example

5
3 2 1 1 2 

4 2 0 0 2

Cho một xâu \(S\) chỉ gồm các chữ cái in thường. Cách mô tả rút gọn của xâu \(S\) như sau:

• Chọn ra một xâu \(X\) ngắn nhất có thể và một số nguyên dương \(K\), sao cho khi viết xâu \(X\) lặp lại \(K\) lần thì ta thu được xâu \(S\)
• Ghép \(K\) và \(X\), ta thu được xâu rút gọn của \(S\).

Ví dụ:

• Xâu rút gọn của “abababab” là “4ab”
• Xâu rút gọn của “aaa” là “3a”
• Xâu rút gọn của “abac” là “1abac”

Input

• Gồm một dòng duy nhất chứa xâu \(S\) có độ dài không quá \(1000\).

Output

• In ra xâu rút gọn của xâu \(S\).

Example

abababab 

4ab

aaa 

3a

abac 

1abac

Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,...,a_N\). Đếm số cặp chỉ số \((i,j)\) thỏa mãn:

• \(1 \le i \le j \le n\);
• \(a_i + a_j^2=K\) với \(K\) cho trước.

Input

• Dòng đầu tiên gồm 2 số nguyên dương \(N\) và \(K\) \((N \le 10^5,K \le 10^9)\)
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^9)\)

Output

• In ra số cặp \((i,j)\) thỏa mãn.

Example

3 5
1 2 2 

2

Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,..,a_N\) và số nguyên dương \(K\). Chọn ra \(K\) phần tử liên tiếp sao cho tổng của chúng là lớn nhất. In ra giá trị đó

Input

• Dòng 1: hai số nguyên dương \(N\) và \(K\) \((K \le N \le 10^5)\);
• Dòng 2: gồm \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^9)\)

Output

• In ra đáp án thỏa mãn yêu cầu đề bài.

Example

6 2
2 4 5 2 9 1 

11

Cho dãy số nguyên gồm \(N\) phần tử. Tìm:

• Dãy con khác rỗng có tổng các phần tử là lớn nhất. (Các phần tử có thể không liên tiếp)
• Dãy con gồm các phần tử liên tiếp có tổng lớn nhất.

Input

• Gồm nhiều test, dòng đầu tiên là số lượng test \(T\) \((1≤T≤10)\)
• Mỗi bộ test gồm hai dòng:
  • Dòng đầu là số nguyên dương \(N\) là số lượng phần tử của dãy \((1≤N≤10^5)\)
  • Dòng tiếp theo gồm \(N\) số nguyên trong khoảng \([−10^4,10^4]\)

Output

• Với mỗi bộ test, in ra trên một dòng, hai số là hai tổng theo yêu cầu.

Example

2
3
4 4 2
5
3 3 -2 3 -4 

10 10
9 7

Cho hai số nguyên dương \(A\) và \(B\). Tìm chữ số tận cùng của \(A^B\).

Input

• Dòng thứ nhất chứa số nguyên dương \(A\).
• Dòng thứ hai chứa số nguyên dương \(B\).

Output

• In ra chữ số tận cùng của \(A^B\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(A, B \leq 10\);
• Subtask \(2\) (\(30\%\) số điểm): \(A, B \leq 10^6\);
• Subtask \(3\) (\(20\%\) số điểm): \(A, B \leq 10^9\);
• Subtask \(4\) (\(10\%\) số điểm): \(A, B \leq 10^{18}\);
• Subtask \(5\) (\(10\%\) số điểm): \(A, B \leq 10^{100000}\);

Example

2
4 

6

Cho một xâu \(S\) có độ dài \(l\) gồm các chữ cái thường. Cho \(Q\) thao tác, mỗi thao tác chỉ gồm một số nguyên dương \(x\), yêu cầu đảo ngược xâu con từ vị trí \(x\) đến vị trí \(l−x+1\). Chú ý: xâu kí tự được đánh số từ 1 đến \(l\).

Input

• Dòng đầu tiên gồm một xâu \(S\) \((1 \leq l \leq 2 \times 10^5)\);
• Dòng thứ hai gồm một số nguyên dương \(Q\) là số thao tác đảo ngược \((Q \leq 10^5)\).
• Dòng thứ ba gồm \(Q\) số nguyên \(x_i\) \((1 \leq x_i \leq l )\)

Output

• In ra xâu cuối cùng, sau khi thực hiện \(Q\) thao tác.

Example

tinteen
3
1 1 3 

tietnen