Cho một số ~N~. Hãy tìm số ~x~ nhỏ nhất mà số ~x~ có tổng các chữ số bằng ~N~.

Yêu cầu: Tìm số ~x~ nhỏ nhất mà tổng các chữ số của nó bằng ~N~

INPUT

• Dòng đầu tiên chứa số ~N~ ~(N <= 10^7)~

OUTPUT

• Một dòng duy nhất là yêu cầu của bài toán

SUBTASKS

• Subtask 1 (40%): ~N <= 10^4~
• Subtask 2 (60%): ~N <= 10^7~

SAMPLE

Input

4

Output

4

Input

12

Output

39

Cho dãy ~A~ gồm ~N~ phần tử.

Một dãy ~a~ là dãy con của dãy ~b~ khi và chỉ khi ta xóa đi một số phần tử trong dãy ~b~ sẽ thu về dãy ~a~.

Cụ thể với ~a = [1, 2, 3]~ sẽ là dãy con của ~b = [1, 4, 5, 2, 10, 3]~. Và dãy ~a~ = [] (rỗng) cũng là một dãy con của ~b = [1, 4, 5, 2, 10, 3]~.

Yêu cầu: Với ~q~ truy vấn, mỗi truy vấn gồm 1 cặp số ~l~ và ~r~ ~(1 <= l <= r <= N)~. Hãy tìm dãy con của dãy ~A_l, A_{l + 1}, ..., A_{r - 1}, A_{r}~ có tổng lớn nhất và in ra tổng đó.

INPUT

• Dòng đầu chứa 2 số ~N~ và ~q~ ~(1 <= N, q, <= 10^5)~
• Dòng thứ 2 chứa dãy ~A~ gồm ~n~ phần tử ~(|A_i| <= 10^7)~
• ~q~ dòng tiếp theo, mỗi dòng gồm 1 cặp số ~l~ và ~r~

OUTPUT

• Với mỗi testcase, in ra yêu cầu của bài

SUBTASKS

• Subtask 1 (40%): ~q <= 10^4, n <= 10^2~
• Subtask 2 (60%): ~q <= 10^5, n <= 10^5~

SAMPLE

Input

7 2
1 -2 3 -4 5 -6 7
1 5
3 6

Output

9
8

Explanation

Dãy con có tổng lớn nhất từ:
1 -> 5: 1 + 0 + 3 + 0 + 5 = 9
3 -> 6: 3 + 0 + 5 + 0 = 8

Cho một số ~N~ với ~n~ là độ dài của số ~N~.

Một số được định nghĩa là Phong Cách nếu nó là bội của 30.

Yêu cầu: Với số ~N~ cho trước hãy tìm hoán vị phong cách lớn nhất của số ~N~. Nếu không tìm ra hãy in ra -1.

INPUT

• Dòng đầu tiên chứa số ~n~ ~(n <= 10^7)~ là độ dài của số ~N~
• Dòng tiếp là số ~N~

OUTPUT

• Gồm ~q~ dòng, mỗi dòng hãy in ra yêu cầu của bài toán

SAMPLE

Input

4
2130

Output

3210

Input

4
1111

Output

-1

Cho dãy ~A~ gồm ~N~ phần tử.

Một số ~x~ được định nghĩa là Lẻ VCL khi và chỉ khi nó xuất hiện lẻ lần trong mảng.

Yêu cầu: Hãy tìm số ~x~ trong dãy ~A~.

Lưu ý: Chỉ có duy nhất 1 số ~x~ trong mảng.

INPUT

• Dòng đầu chứa số ~N~ ~(N <= 10^7)~
• Dòng thứ 2 chứa dãy ~A~ gồm ~N~ phần tử ~(A_i <= 10^9)~

OUTPUT

• Gồm một dòng duy nhất là yêu cầu của bài toán

SAMPLE

Input

5
1 2 1 2 3

Output

3

Input

3
9 5 9

Output

5

Một số được định nghĩa là số bán nguyên tố khi và chỉ khi nó chỉ có 3 ước.

Yêu cầu: Với ~q~ truy vấn cho trước hãy kiểm tra xem ~n~ có phải số bán nguyên tố hay không? Nếu có hãy in ra 1 ngược lại in ra 0.

INPUT

• Dòng đầu chứa số ~q~ ~(q <= 10^5)~
• ~q~ dòng tiếp theo, mỗi dòng chứa số ~n~ ~(n <= 10^{12})~

OUTPUT

• Gồm ~q~ dòng, mỗi dòng hãy in ra yêu cầu của bài toán

SUBTASKS

• Subtask 1 (30%): ~q <= 10^5, n <= 10^3~
• Subtask 2 (30%): ~q <= 10^5, n <= 10^6~
• Subtask 3 (40%): ~q <= 10^5, n <= 10^{12}~

SAMPLE

Input

3
1
3
4

Output

0
0
1

Explanation

Các ước của: 
1: 1
3: 1 3
4: 1 2 4