Tí rất đam mê Tin học nên đăng ký vào nhóm bồi dưỡng của thầy giáo ở trường. Thầy giáo kiểm tra năng lực của Tí bằng cách yêu cầu Tí thực hiện giải bài toán sau: "Cho hai số nguyên dương a và b. Hãy tính tổng tất cả các số vừa chia hết cho 2, vừa chia hết cho 3 trong đoạn [a,b].

Yêu cầu: Em hãy viết chương trình giúp Tí giải quyết bài toán trên.

Input

• Gồm một dòng ghi hai số nguyên dương ~a~ và ~b~ (~a≤b≤10^9~).

Output

• Gồm một số nguyên dương là tổng tính được.

Example

Input

2 15

Output

18

Trong mặt phẳng toạ độ Oxy, cho ba điểm không trùng nhau và không cùng nằm trên một đường thẳng, tạo thành một tam giác: A có toạ độ (x1, y1), B có toạ độ (x2, y2) và C có toạ độ (x3, y3).

Yêu cầu: Viết chương trình kiểm tra xem tam giác ABC có phải là tam giác vuông hay không?

Input

• Gồm 6 số nguyên x1, y1, x2, y2, x3, y3. (~-10^9≤x_1,y_1,x_2,y_2,x_3,y_3≤10^9~).

Output

• In ra "TAM GIAC VUONG" nếu kiểm tra tam giác ABC là tam giác vuông; ngược lại ghi "KHONG PHAI TAM GIAC VUONG".

Examples

Input1

0 0 0 1 2 0

Outpu1t

TAM GIAC VUONG

Input2

1 2 3 4 5 6

Output2

KHONG PHAI TAM GIAC VUONG

Cho dãy số tự nhiên N, ta có một dãy số A gồm các số tự nhiên từ 1 đến N. Phép nén dãy là số là là tạo ra dãy số mới mà các phần tử được tạo ra bằng cách cộng hai số cạnh của dãy số ban đầu. Mỗi lần nén dãy số, dãy số mới sẽ ít hơn dãy số ban đầu một phần. Ta nén dãy số đến khi còn một phần tử, phần tử đó là giá trị của dãy số. Ví dụ: ~N = 4~ ta có kết quả cuối cùng là số~ 20~.

Dãy ban đầu : 1 2 3 4

Nén lần 1: 3 5 7

Nén lần 2: 8 12

Nén lần 3: 20

Yêu cầu: Viết chương trình xấu ra giá trị nén của dãy . Vì kết quả có thể rất lớn, nên chỉ cần xuất ra số dư của phép chia giá trị nén của dãy số ~10^9~.

Input

• Nhập số nguyên ~N~ (~1≤N≤400~) .

Output In ra số dư của phép chia giá trị nén của dãy số cho hay (~10^9~).

Examples

Input1

4

Output1

20

Input2

15

Output2

131072

Sau cuộc thi tìm hiệu kiến thức về Tin học về Internet. Trong toàn thể các bạn tham gia cuộc thi có n bạn nam và m bạn nữ. Ban Tổ chức muốn tặng thêm các phần quà theo nhóm, với số lượng nhóm nhiều nhất có thể và số lượng nam, nữ phải bằng nhau giữa các nhóm.

Yêu cầu: Bạn hãy giúp Ban Tổ chức chia nhóm như trên, để biết được: Tối đa có bao nhiêu nhóm, mỗi nhóm có bao nhiêu nam và bao nhiêu nữ?

Input

• Gồm hai số nguyên ~n~, ~m~ cách nhau một khoảng trắng (~1<n~,~m<10^9~).</li>

Output

• Dòng một ghi số lượng nhóm tối đa có thể chia.

• Dòng hai ghi 2 số tương ứng là số nam và số nữ của mỗi nhóm.

Example

Input

24 36

Output

12
2 3

Cho một dãy gồm ~n~ số nguyên dương, các phần tử được đánh số thứ tự từ 1 đến ~n~. Một phần tử được gọi là phần tử trung bình nếu nó có hai phần tử kề bên và bằng trung bình cộng của hai phần tử kề bên của nó, phần tử thứ i có hai phần tử kề bên là phần tử thứ ~i-1~ và phần tử thứ ~i+1~.

Yêu cầu: Xác định xem có bao nhiêu phần tử trung bình trong dãy số này.

Input

• Dòng thứ nhất ghi số nguyên dương ~n~ (~n≤10^3~)

• Dòng thứ hai ghi ~n~ số nguyên dương ~a_i~ (~1≤a_i≤10^3~).

Output

• Một số duy nhất là kết quả tìm được.

Example

Input

8
2 2 2 5 8 3 5 7

Output

3

Cho một dãy gồm ~n~ số nguyên dương.

Yêu cầu: Xác định số cách chọn hai phần tử trong dãy số sao cho tổng hai phần tử này có giá trị chẵn.

Input

• Dòng thứ nhất ghi số nguyên dương ~n~ (~1≤n≤10^5~).

• Dòng thứ hai ghi ~n~ số nguyên dương ~a_i~ (~1≤a_i≤10^3~).

Output

• Một số là kết quả tìm được.

Examples

Input1

5
2 7 1 4 2

Output1

4

Input2

5
2 4 7 8 6

Output2

6

Note

• Giải thích ví dụ 1: Các cặp số được chọn là (2;4),(2;2),(4;2),(7;1).

• Giải thích ví dụ 2: Các cặp số được chọn là (2;4),(2;8),(2;6),(4;8),(4;6),(8;6).

Cho một mảng số nguyên ~A~ có ~N~ phần tử, mảng này đã được sắp xếp tăng dần. Hãy tìm vị trí của hai phần tử khác nhau bất kỳ sao cho tổng của chúng có giá trị là ~X~. Nếu trong dãy ~A~ không tồn tại hai phần tử khác nhau có tổng là ~X~ thì in ra "No solution".

Input

• Dòng đầu chứa 2 số nguyên ~N~ và ~X~.
• Dòng tiếp theo chứa ~N~ số nguyên ~A_i~.

Output

• Hai vị trí ~i~ và ~j~ khác nhau và xa nhau nhất có thể sao cho tổng ở hai vị trí này có giá là ~X~. In vị trí phần tử nhỏ hơn trước phần tử lớn hơn.
• Nếu không tồn tại in ra "No solution".

Constants

~N \le 10^6; A_i,X \le 10^9~

Example

Output

6 16
2 3 5 7 9 12

Output

4 5

Cho dãy số nguyên dương a có n phần tử. Hãy tìm độ dài đoạn con dài nhất trong dãy sao cho tổng các phần tử trong đoạn này không quá s. Dữ liệu đảm bảo các phần tử trong dãy a đều có giá trị không quá s.

Input:

• Dòng 1. Ghi 2 số nguyên dương n, s.
• Dòng 2. Ghi n số nguyên ~a_1, a_2,...,a_n~

Output:

• Ghi ra độ dài của dãy con dài nhất thoả mãn yêu cầu trên.

Example:

Input:

7 20
2 6 5 3 6 8 9

Output:

4

Constraints:

~n \le 10^6; 0 \le a_i \le 10^9; s \le 10^{18}~

Để chuẩn bị cho hội trại sắp tới, lớp Nam được giao nhiệm vụ cắt ~N~ (~1≤N≤10^5~) đoạn dây dùng để dựng trại đá thành ~K~ đoạn dây bằng nhau. Mỗi đoạn dây đã cắt có thể có phần thừa khác 0 và có thể không cần cắt hết các đoạn dây đã cho. Bạn hãy giúp lớp Nam xác định đoạn dây có độ dài lớn nhất có thể cắt. Nếu không có cách cắt thì xuất ra số 0.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ (~K≥0~).

• ~N~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~a_i~ (~1≤a_i≤10^9~), là chiều dài của đoạn dây thứ ~i~.

Output

• Một số nguyên là độ dài lớn nhất của đoạn dây thu được.

Scoring

• Có 50% số test ứng với ~N≤1000~

• Có 50% số test ứng với ràng buộc đề bài

Example

Input

4 11
802
743
457
539

Output

200

Một học sinh chuẩn bị cho năm học mới của mình nên đã đi đến một cửa hàng mua viết và tập. Trong hai lần mua sắm, học sinh đều mua cùng số lượng viết và cùng số lượng tập. Tuy nhiên, trong hai lần mua sắm này, học sinh mua viết và tập khác loại nhau nên đơn giá có thể không giống nhau.

Trong lần mua thứ nhất, học sinh mua với đơn giá viết là ~v1~ đồng và đơn giá tập là ~t1~ đồng. Tổng số tiền phải trả trong lần này là ~s1~ đồng.

Trong lần mua thứ hai, học sinh mua với đơn giá viết là ~v2~ đồng và đơn giá tập là ~t2~ đồng. Tổng số tiền phải trả trong lần này là ~s2~ đồng.

Yêu cầu: Xác định tổng số lượng viết và tổng số lượng tập mà học sinh đã mua trong cả hai lần.

Input

• Dòng đầu chứa ba số nguyên dương ~v1~,~t1~,~s1~, lần lượt cho biết đơn giá viết, đơn giá tập và tổng số tiền phải trả trong lần mua thứ nhất.

• Dòng thứ hai chứa ba số nguyên dương ~v2~,~t2~,~s2~, lần lượt cho biết đơn giá viết, đơn giá tập và tổng số tiền phải trả trong lần mua thứ hai.

Lưu ý: Các số có giá trị không vượt quá ~10^9~, dữ liệu cho đảm bảo luôn tìm được đúng một đáp án và đáp án luôn có giá trị là số nguyên không âm.

Output

• Hai số nguyên tương ứng với tổng số lượng viết và tổng số lượng tập mà học sinh đã mua.

Example

Input

7000 10000 78000
6500 11000 81000

Output

8 10

Cho ~N~ (~1≤N≤20~) phương trình bậc nhất có dạng: ~ax+b=0~ (~a≠0~), hai số nguyên ~a~, ~b~ (~|a|,|b|≤10^{12}~) được gọi là hệ số của phương trình, ~x~ là ẩn số.

Yêu cầu: Hãy đếm số lượng phương trình có nghiệm nguyên dương, đồng thời nghiệm đó là số nguyên tố.

Input

• Dòng thứ nhất chứa số nguyên dương ~N~.
• ~N~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~a~ và ~b~, cách nhau một khoảng trắng

Output

• Xuất ra màn hình một số nguyên là số lượng phương trình có nghiệm thỏa mãn yêu cầu bài toán

Example

Input

3
1 -3
12 -6
-50 -100

Output

1

Nghệ nhân nấu ăn Sơn Mập có thể sử dụng hệ thống gồm ~n~ bếp điện để thực hiện nấu món ăn khiến ông được vinh danh, đó là món "Gatô hải sản". Thời gian để thực hiện nấu một suất ăn như vậy trên các bếp điện tương ứng là ~t_1, t_2, …, t_n~ giây.

Yêu cầu: Cho biết ~s~ là số lượng thực khách cần phục vụ, hãy xác định thời gian tối thiểu cần thiết để Nghệ nhân Sơn Mập có thể nấu xong ~s~ suất ăn trên hệ thống bếp điện của khách sạn. Để nấu mỗi suất ăn chỉ được sử dụng một bếp.

Input:

• Dòng đầu tiên chứa 2 số ~s~ và ~n~ lượng suất ăn ~s~ và số lượng bếp điện ~n~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~t_1, t_2, …, t_n~.

Output:

• In ra một số nguyên là thời gian tối thiểu tìm được tính bằng giây.

Example:

Input:

3 2
50 70                  

Output:

100

Constraints:

~0 < n \le 10^5; 0 < s < 10^6; 1 \le t_i \le \le 10^9~

Tại sân bay Đồng Hới, một đoàn khách gồm M người chuẩn bị tham gia chuyến bay. Vì số lượng khách quá lớn nên điểm kiểm soát của sân bay đã được tăng lên thành N điểm. Tại điểm kiểm soát thứ i, cần mất ~A_i~ (s) để có thể kiểm tra xong một người (tính cả thời gian đi bộ từ địa điểm xếp hàng tới điểm kiểm tra này). Các hành khách sắp xếp theo một hàng đợi. Lần lượt từng người vào một. Hành khách ở đầu hàng đợi được phép đi vào một trạm kiểm soát nào đó nếu như trạm kiểm soát đó đang trống. Tuy nhiên, người đó cũng có quyền đứng chờ để đợi một trạm kiểm soát khác trống để đi tới trạm đó, vì có thể giảm thiểu chi phí thời gian cho cả đoàn.

Yêu cầu: Các bạn hãy tính toán xem thời gian nhỏ nhất có thể để đoàn hành khách kiểm tra xong hành lý là bao nhiêu?

Input:

• Dòng đầu tiên gồm 2 số nguyên N và M, lần lượt là số quầy gửi đồ và số vị khách.
• Dòng 2 ghi N số nguyên ~A_1, A_2,...,A_N~ lần lượt là thời gian kiểm tra xong một người của trạm thứ i.

Output:

• In ra đáp số của bài toán.

Example:

Input:

2 6 
7 10

Output:

28

Constraints:

~1 \le A_i \le 10^9 ; N \le 10^5, M \le 10^6~

Bờm được nhận vào làm việc cho nhà Phú Ông và nhiệm vụ chính của cậu ta là chăn trâu. Với bản tính ham chơi nên cậu ta đã quyết định đóng N cái cọc và cột các con trâu vào đó, vì vậy cậu ta thỏa thích chơi đùa mà không sợ các con trâu đi mất. N cái cọc được đặt trên một đường thẳng ở các vị trí ~x_1, x_2, …, x_n~. Phú Ông giao cho Bờm chăn thả C con trâu. Những con trâu này không thích bị buộc vào những chiếc cọc gần các con trâu khác. Chúng trở nên hung dữ khi bị buộc gần nhau, vì chúng cho rằng con trâu kia sẽ tranh giành cỏ của mình.

Để tránh việc các con trâu làm đau nhau, Bờm muốn buộc mỗi con trâu vào một cái cọc, sao cho khoảng cách nhỏ nhất giữa hai con trâu bất kì là lớn nhất có thể.

Yêu cầu: Hãy tìm giá trị lớn nhất này.

Input:

• Dòng 1: Ghi hai số nguyên dương N và C.

• Dòng 2: Ghi N chứa một số nguyên ~x_1,x_2,...,x_N~, với ~x_i~ mô tả vị trí của một cây cọc. Đương nhiên không có hai cây cọc nào cùng một vị trí.

Output:

• In ra giá trị lớn nhất của khoảng cách nhỏ nhất giữa hai con trâu bất kì.

Example:

Input:

5 3 
1 2 8 4 9 

Output:

3

Constraints:

~2 \le C \le N \le 10^5); 0 \le x_i \le 10^9~

ho ba số tự nhiên ~a~, ~b~ và ~n~. Gọi ~S~ là tổng các số tự nhiên nhỏ hơn ~n~, sao cho các số đó chia hết cho ~a~ nhưng không chia hết cho ~b~.

Yêu cầu: Viết chương trình xuất ra màn hình giá trị ~S~.

Input

• Dòng thứ nhất là số tự nhiên ~a~ (~1≤a≤10^4~).
• Dòng thứ hai là số tự nhiên ~b~ (~1≤b≤10^4~).
• Dòng thứ ba là số tự nhiên ~n~ (~1≤n≤10^9~).

Output

• Xuất ra màn hình giá trị ~S~.

Example

Input

2
3
9

Output

14