Nhóm học sinh trường THPT X đang tiến hành nghiên cứu chế tạo robot mới. Trên mặt phẳng tọa độ ~Oxy~ robot đang ở điểm xuất phát có tọa độ (~x_1, y_1~) và nó cần đi đến điểm có tọa độ (~x_2, y_2~). Trong mỗi bước đi, nếu robot đang ở điểm (~x, y~) thì nó có thể đi đến một trong các vị trí (~x-1~, ~y-1~), (~x-1~, ~y~), (~x-1~, ~y+1~), (~x~, ~y-1~), (~x~, ~y+1~), (~x+1~, ~y-1~), (~x+1~, ~y~), (~x+1~, ~y+1~) (Tức là thay đổi giá trị của hoành độ hoặc tung độ hoặc cả hai, bằng cách tăng hoặc giảm ~1~ đơn vị). Tìm số bước tối thiểu mà robot cần thực hiện để đến được vị trí đích.

Input

Từ tệp ROBOT.INP có cấu trúc như sau:

• Dòng đầu tiên chứa ~2~ số nguyên (~x_1, y_1~) là tọa độ vị trí xuất phát của robot.

• Dòng thứ hai chứa ~2~ số nguyên (~x_2, y_2~) là tọa độ vị trí đích của robot

Ràng buộc: ~-10^9~ ~\le~ ~x_1~, ~y_1~, ~x_2~, ~y_2~ ~\le~ ~10^9~

Output

Ghi ra tệp ROBOT.OUT:

• In ra số nguyên ~d~ là số bước tối thiểu để robot đến được vị trí đích

Sample Input 1

0 0
4 5

Sample Output 1

5

Sample Input 2

3 4
6 1

Sample Output 2

3

Đội Trúc Xanh gồm ~3~ bạn An, Thùy và Minh về đầu trong cuộc thi về ca dao — tục ngữ Việt Nam. Cách trao giải của Ban tổ chức cũng khá độc đáo. Trên bàn bày một dãy ~n~ túi kẹo, trên túi kẹo thứ ~i~ có ghi số nguyên ~a_i~ là số lượng kẹo trong túi ~(a_i \ge 0)~. Đội thắng cuộc được phép chọn các túi kẹo có số lượng chia hết cho ~3~.

Đội Trúc Xanh quyết định sẽ chọn hết tất cả các túi có kẹo và được phép lấy. Sau đó từ mỗi túi mỗi người ăn một chiếc kẹo. Phần kẹo còn lại được tập trung và chia đều để mỗi bạn mang về cho em ở nhà.

Yêu cầu: Hãy xác định, mỗi bạn đã ăn bao nhiêu cái kẹo và mang về nhà bao nhiêu cái.

Input

Từ tệp văn bản CANDIES.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.

• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~0 \le a_i \le 10^4, i = 1 \div n~).

Output

Ghi ra tệp văn bản CANDIES.OUT gồm hai số nguyên là số lượng kẹo mỗi bạn đã ăn và số kẹo mỗi bạn mang về, mỗi số đưa ra trên một dòng.

Scoring

Sample Input 1

9
25 16 11 12 14 0 8 30 21

Sample Output 1

3
18

Trên một vách đá có ghi rất nhiều các con số bí ẩn mà chúng có mối liên hệ với số ~30~. Sau một thời gian nghiên cứu, các chuyên gia đã tìm được cách giải mã các số đó như sau: Hoán vị các chữ số của số bí ẩn để thu được một bội số lớn nhất của ~30~.

Hãy viết chương trình để giúp các chuyên gia giải mã các số bí ẩn đó.

Input

Cho trong tệp MATMA.INP gồm một dòng duy nhất chứa số nguyên dương ~N~, với ~N~ có tối đa ~10^7~ chữ số là số cần giải mã.

Output

Ghi ra tệp MATMA.OUT một số nguyên duy nhất, là số lớn nhất chia hết cho ~30~, tìm được bằng cách hoán vị các chữ số của ~N~. Nếu không tìm thấy thì đưa ra ~-1~ (âm một).

Sample Input 1

1002

Sample Output 1

2100

Sample Input 2

12498567859

Sample Output 2

-1

Notes

• Ở ví dụ đầu tiên, số ~2100~ là hoán vị lớn nhất của số ~1002~ và chia hết cho ~30~.

• Ở ví dụ thứ hai, không tồn tại số hoán vị nào chia hết cho ~30~.

Cho ~2~ dãy số nguyên ~a~, ~b~ đều gồm ~n~ phần tử. Ban đầu tất cả các phần tử của dãy ~a~ đều bằng ~0~. Cần biến dãy ~a~ thành dãy ~b~ bằng cách thực hiện một số lần thao tác sau:

• Chọn ra ~k~ phần tử của dãy ~a~ và tăng mỗi phần tử thêm ~1~ đơn vị.

Yêu cầu: Kiểm tra xem có thể biến dãy ~a~ thành dãy ~b~ được hay không?

Input

Từ tệp văn bản EQLARRAY.INP gồm nhiều test có cấu trúc như sau:

• Dòng đầu tiên của tệp chứa số nguyên dương ~Q~ là số test ~(1 \le Q \le 1000)~.

• Tiếp theo là các test có cấu trúc như sau: Dòng đầu tiên của mỗi test chứa hai số nguyên dương ~n~ và ~k~ ~(1 \le k \le n \le 10^5)~.

• Dòng thứ hai của mỗi test chứa dãy số nguyên ~b~ (~1 \le b_i \le 10^9, i = 1 \div n~).

Ràng buộc: Tổng các số ~n~ trong tất cả các test không vượt quá ~10^6~.

Output

Ghi ra tệp văn bản EQLARRAY.OUT với mỗi test, in kết quả trên một dòng, in "YES" nếu dãy ~a~ có thể biến thành dãy ~b~ và "NO" nếu ngược lại.

Sample Input 1

2
5 3
1 2 3 4 5
3 2
1 1 4

Sample Output 1

YES
NO

Trò chơi Mario bao gồm nhân vật hoạt hình Mario và các cây nấm được thiết kế trên một trục số nằm ngang. Có ~N~ cây nấm, cây thứ ~i~ đặt ở vị trí có tọa độ ~X_i~ và chứa ~W_i~ sức mạnh. Mario đang đứng ở vị trí ~X~, có thể di chuyển theo chiều dương hay âm của trục số tùy ý. Nếu đi qua cây nấm ~i~, nó sẽ ăn cây nấm đó và sẽ được tăng thêm ~W_i~ sức mạnh, đồng thời cây nấm ~i~ sẽ biến mất.

Yêu cầu: Thực hiện một lượt chơi để Mario ăn được nhiều sức mạnh nhất, biết rằng mỗi lượt chơi thì Mario chỉ có thể di chuyển quãng đường dài tối đa bằng ~K~.

Input

Từ tệp văn bản MARIO.INP gồm 2 dòng có cấu trúc như sau:

• Dòng thứ nhất chứa ba số nguyên ~N~, ~X~ và ~K~ (~1 \leq N \leq 10^5, |X| \leq 10^6, 1 \leq K \leq 10^9~).

• Dòng thứ ~i~ trong ~N~ dòng tiếp theo chứa ~2~ số nguyên ~X_i~ và ~W_i~ (~|X_i| \leq 10^6, 1 \leq W_i \leq 10^9~).

Output

Ghi ra tệp văn bản MARIO.OUT một số nguyên duy nhất là tổng sức mạnh tối đa Mario ăn được từ các cây nấm sau một lượt chơi.

Scoring

Subtask	Điểm	Giới hạn
1	~50~	~N \leq 10^4~
2	~50~	Không có ràng buộc gì thêm

Sample Input 1

4 3 7
0 9
4 1
5 5
7 8

Sample Output 1

15