Cho ba số nguyên dương ~s,d,m (s≤10^6;d≤9;m≤9)~. Hãy tìm số nguyên dương ~N~ nhỏ nhất thỏa mãn các điều kiện:

• Tổng các chữ số của ~N~ bằng ~s~.
• Các chữ số của ~N~ đều xuất hiện chẵn lần và là tập con của tập các chữ số từ 0 đến ~d~ (~N~ không được bắt đầu bằng chữ số 0);
• Số ~N~ chia hết cho ~m~.

Dữ liệu:

• Vào từ thiết bị vào chuẩn gồm một dòng chứa ba số nguyên dương s,d,m.

Kết quả:

• Ghi ra thiết bị ra chuẩn một dòng chứa số nguyên dương N tìm được hoặc ghi số -1 nếu không tồn tại số N thỏa mãn.

Ràng buộc:

• Có 20% số test ứng với 20% số điểm có ~m=1;s≤100;~
• Có 30% số test khác ứng với 30% số điểm có ~s≤100;~
• Có 30% số test khác ứng với 30% số điểm có ~s≤1000;~
• Có 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.

Sample Test:

Input:

6 5 4

Output:

1212

Cho hai hình chữ nhật có các cạnh song song với các trục toạ độ. Tính diện tích phần giao nhau của hai hình chữ nhật đó.

INPUT

8 số ax, ay, bx, by, cx, cy, dx, dy lần lượt là toạ độ hai đỉnh của hai góc đối của một hình chữ nhật, có giá trị không quá ~10^8~

OUTPUT

Số nguyên không âm duy nhất là diện tích phần giao nhau của hai hình chữ nhật. Nếu hai hình chữ nhật không có phần giao nhau đưa ra số ~0~

SAMPLE INPUT

-2 3 2 1 3 4 0 2

SAMPLE OUTPUT

2

Để chào đón sự trở về của các anh hùng Đội tuyển quốc gia Việt Nam, thtb8 muốn phamgiaminh trả lời ~T~ bài toán, bài toán thứ ~i~ gồm hai số nguyên dương ~l_i~ và ~r_i~. Gọi tập các số nguyên tố nằm trong khoảng giữa ~l_i~ và ~r_i~ được sắp xếp theo thứ tự tăng dần là

~S =~ {~p_1,p_2,...,p_k~}. thtb8 cần phamgiaminh tính công thức sau:

Vì kết quả có thể rất lớn nên thtb8 muốn phamgiaminh trả lời các kết quả là phần dư khi chia cho ~10^9+7~. phamgiaminh khá buồn vì Park Hang Seo chia tay VN nên muốn nhờ các bạn giúp phamgiaminh trả lời các bài toán đó.

Dữ liệu

• Dòng đầu tiên ghi một số nguyên dương ~T~ là số lượng bài toán.

• Dòng thứ ~i~ trong ~T~ dòng tiếp theo gồm ~2~ số nguyên dương ~l_i~ và ~r_i~.

• ~l_i,r_i, T ≤ 10^6~

Kết quả

• In ra ~T~ dòng, dòng thứ ~i~ là kết quả của bài toán thứ ~i~.

Sample

Input

2
1 5
3 7

Output

23
34

Cho dãy số nguyên ~a~ gồm ~n~ phần tử. Hãy tính tổng của ~|a_i-a_j|~ với mọi cặp ~(i,j)~ thỏa mãn ~1 \le i < j \le n~.

Input

• Dòng đầu gồm ~1~ số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng sau gồm ~n~ số nguyên miêu tả dãy ~a~ ~(|a_i| \le 10^6)~

Output

• In ra kết quả tìm được.

Sample Test

Input

3
5 1 2

Output

8

Quang là một tài xế xe buýt đi từ trạm ~1~ đến trạm thứ ~p~. Thời gian để di chuyển qua các trạm là ~1~ phút. Cho biết thời gian và địa điểm chờ của ~n~ hành khách đón xe buýt, hãy giúp Quang xác định thời gian xuất phát từ trạm thứ ~1~ sớm nhất để có thể đón ít nhất ~m~ hành khách. Biết rằng xe buýt có sức chứa không giới hạn.

Dữ liệu

• Dòng thứ nhất ghi hai số nguyên dương ~n, m, p~ số hành khách chờ xe buýt, số hành khách ít nhất Quang phải đón và số trạm xe buýt.

• ~n~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~a_i~ và ~b_i~ (~1 ≤ a_i ≤ p, b_i ≤ 10^9~) − khách hàng thứ ~i~ bắt đầu chờ tại trạm ai tại thời điểm ~b_i~.

Kết quả

In ra thời điểm xuất phát từ trạm ~1~ sớm nhất để Quang có thể đón ít nhất ~m~ hành khách.

Ví dụ

Input

7 4 5               
1 1
2 4
4 10
5 8
3 5
5 6
4 7

Output

3

Giải thích

Nếu Nam xuất phát tại thời điểm ~3~ thì sẽ đón được hành khách thứ ~1, 2, 5~ và ~6~.