Cho số nguyên không âm ~n~, cần tìm số ~m~ nhỏ nhất thỏa mãn điều kiện:

• Số ~m~ lớn hơn hoặc bằng ~n~;
• Tổng các chữ số của ~m~ nhỏ hơn tổng các chữ số của ~n~;

Dữ liệu: Vào từ thiết bị vào chuẩn có dạng:

• Dòng đầu chứa số nguyên dương ~t~ là số bộ dữ liệu;
• Dòng thứ ~i~ (~1 \le i \le t~) chứa một số nguyên không âm ~n~.

Kết quả: Ghi ra thiết bị ra chuẩn gồm ~t~ dòng, mỗi dòng là số ~m~ tương ứng tìm được, nếu không tồn tại số đưa ra ~-1~.

Ví dụ:

Subtask 1 (60 điểm): ~n \le 10^6; t \le 3~;
Subtask 2 (20 điểm): ~n \le 10^6; t \le 3 \times 10^4~;
Subtask 3 (20 điểm): ~n \le 10^{16}; t \le 3 \times 10^4~;

Cho ~n + 1~ hình chữ nhật trên mặt phẳng ~Oxy~, các hình chữ nhật đều có các cạnh song song hoặc vuông góc với trục toạ độ. Hãy tìm điểm ~(x, y)~ nằm trong ít nhất ~n~ hình chữ nhật đã cho. Điểm ~(x, y)~ được gọi là nằm trong hình chữ nhật xác định bởi hai điểm ~(x_1, y_1)~ và ~(x_2, y_2)~ nếu:

• ~min(x_1, x_2) \le x \le max(x_1, x_2)~;
• ~min(y_1, y_2) \le y \le max(y_1, y_2)~.

Dữ liệu: Vào từ thiết bị vào chuẩn có dạng:

• Dòng đầu chứa số nguyên ~n~ (~1 \le n \le 2 \times 10^5~);
• ~n + 1~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên ~x_1, y_1, x_2, y_2~ (~0 \le x_1, y_1, x_2, y_2 \le 10^9~) mô tả hai điểm ~(x_1, y_1)~ và ~(x_2, y_2)~ là hai góc của hình chữ nhật, dữ liệu đảm bảo hai điểm này là phân biệt.

Kết quả: Ghi ra thiết bị ra chuẩn hai số nguyên ~x, y~ là toạ độ của điểm nằm trong ít nhất ~n~ hình chữ nhật, nếu có nhiều điểm thoả mãn thì đưa ra điểm có ~x~ nhỏ nhất, nếu có nhiều điểm thoả mãn có cùng ~x~ nhỏ nhất thì đưa ra điểm có ~y~ nhỏ nhất. Nếu không có điểm nào thỏa mãn chỉ ghi ~-1~.

Ví dụ:

Subtask 1 (25 điểm): ~x_1, x_2, y_1, y_2 \le 20~;
Subtask 2 (25 điểm): ~x_1, x_2, y_1, y_2 \le 1000~;
Subtask 3 (25 điểm): ~n \le 2000~;
Subtask 4 (25 điểm): Không có ràng buộc gì thêm.

Cho một dãy gồm ~n~ số nguyên ~a_1, a_2, a_3, \ldots, a_n~. Tìm đoạn con liên tiếp dài nhất có tổng không âm.

Input

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

Output

In ra độ dài đoạn con thoả mãn. Nếu không tồn tại đoạn con thoả mãn in ra -1.

Subtasks

• Subtask ~1~ (~50\%~): ~n \leq 10^3~.
• Subtask ~2~ (~50\%~): Không có điều kiện gì thêm.

Sample Test

Input:

5
-1 -1 2 -2 -3

Output:

3

Cho dãy ~a~ gồm ~n~ số nguyên. Đếm số lượng đoạn con liên tiếp chia hết cho ~n~.

Input

• Dòng đầu tiên chứa số nguyên ~n~.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~.

Output

• In ra kết quả của bài toán.

Constraints

• ~1 \leq n \leq 2 \times 10^5~.
• ~-10^9 \leq x, a_i \leq 10^9~.

Sample Test

Bạn cần phải đặt ~8~ quân hậu lên một bàn cờ vua, sao cho không có hai quân hậu nào tấn công lẫn nhau. Để tăng phần thử thách, mỗi ô vuông sẽ được đánh dấu là ô trống hoặc ô bị cấm, và bạn chỉ được xếp các quân hậu trên những ô trống. Tuy nhiên, những ô bị cấm không chặn đường chiếu của các quân hậu.

Có bao nhiêu cách để đặt các quân hậu?

Input

• Gồm ~8~ dòng, mỗi dòng chứa ~8~ kí tự. Mỗi ô vuông là trống nếu kí tự tại đó là ., hoặc bị cấm nếu là *.

Output

• In ra một số nguyên: số lượng cách xếp hậu.

Example

Sample input

........
........
..*.....
........
........
.....**.
...*....
........

Sample output

65