Chữ số tận cùng của 1 số là chữ số cuối cùng của số đó. Ví dụ: số \(\textbf{123}\) có chữ số tận cùng là \(\textbf{3}\); số \(\textbf{5}\) có chữ số tận cùng là \(\textbf{5}\).

Cho 2 số nguyên dương \(\textbf{A, N}\), hãy tìm chữ số tận cùng của \(\mathbf{A^{N}}\).

Input

• Gồm một dòng duy nhất ghi 2 số nguyên dương lần lượt là \(\textbf{A}\) và \(\textbf{N}\). Các số viết cách nhau một dấu cách.

Output

• Gồm một số nguyên duy nhất là chữ số tận cùng tìm được.

Scoring

• Có 60% số điểm tương ứng với: \(1 \leq A, N \leq 9\);
• Có 20% số điểm tương ứng với: \(1 \leq A, N \leq 15\);
• Có 20% số điểm tương ứng với: \(1 \leq A, N \leq 10^{8}\);

Example

2 10

4

12 3

8

Trọng số của một xâu S là trung bình cộng các chữ số trong xâu S đó. Nếu xâu S không có chữ số nào thì trọng số là 0. Ví dụ: Xâu ab011c2 có trọng số là 1.

Cho N xâu kí tự, hãy tìm xâu có trọng số lớn nhất. Nếu có nhiều xâu có trọng số bằng nhau thì ghi ra xâu đầu tiên tìm được, nếu không tìm thấy xâu có trọng số lớn nhất thì ghỉ 0.

Input

• Dòng đầu ghi số nguyên dương N (\(\mathbf{1 \leq N \leq 100}\)) là số lượng xâu.

Output

• Gồm một dòng duy nhất in ra xâu tìm được.

Scoring

• Có 60% số điểm tương ứng với xâu S có độ dài không quá 255;
• Có 40% số điểm tương ứng với xâu S có độ dài không quá 1000;

Example

3
aaaaaaa
10a3bb2021
100256

100256

Một số nguyên dương \(X\) được gọi là số đặc biệt nếu thỏa mãn hai điều kiện sau:

• \(X\) là số nguyên tố
• Số lượng chữ số chẵn và số lượng chữ số lẻ trong \(X\) là khác nhau.

Cho một dãy số nguyên gồm \(N\) phần tử \(A_{1}, A_{2}, ..., A_{N}\). Hãy đếm số lượng phần tử là số đặc biệt của dãy \(A\).

Input

• Dòng thứ nhất ghi số nguyên dương \(N\);
• Dòng thứ hai chứa \(N\) số nguyên \(A_{1}, A_{2}, ..., A_{N}\). Các số cách nhau một dấu cách.

Output

• Gồm một số nguyên duy nhất là số lượng số đặc biệt đếm được.

Scoring

• Có 60% số điểm tương ứng với: \(1 \leq N \leq 300\); \(1 \leq A_{i} \leq 50000\);
• Có 20% số điểm tương ứng với: \(1 \leq N \leq 300\); \(|A_{i}| \leq 10^{12}\);
• Có 20% số điểm tương ứng với: \(1 \leq N \leq 2 * 10^{6}\); \(|A_{i}| \leq 2 * 10^{6}\);

Example

5
121 311 122 23 241

2

An thích học về bảng số. Bạn ấy tạo ra bảng số \(A\) có kích thước \(M * N\) theo quy luật như sau:

• Bảng có \(M\) dòng đánh số từ \(1\) đến \(M\);
• Bảng có \(N\) cột đánh số từ \(1\) đến \(N\);
• Tại vị trí dòng \(i\) và cột \(j\) trên bảng số sẽ được ghi số \((i - 1) * N + j\) nếu (\(i + j\)) là số chẵn, và ghi số \(0\) nếu (\(i + j\)) là số lẻ (\(1 \leq i \leq M, 1 \leq j \leq M\)).

Cho hai số nguyên dương \(M, N\). Hãy tính tổng tất cả các số được ghi trên bảng.

Input

• Gồm một dòng duy nhất ghi 2 số nguyên dương lần lượt là \(M, N\). Các số viết cách nhau một dấu cách.

Output

• Gồm một số nguyên duy nhất là tổng các số được ghi trên bảng số. Vì số này có thể rất lớn nên chỉ in đáp án ra sau khi chia lấy dư cho \(1532023\).

Scoring

• Có 60% số điểm tương ứng với: \(1 \leq M, N \leq 500\);
• Có 20% số điểm tương ứng với: \(1 \leq M, N \leq 10^{5}\);
• Có 20% số điểm tương ứng với: \(1 \leq M, N \leq 10^{9}\);

Example

3 4

38