Cho dãy ~A~ gồm ~N~ số nguyên không âm ~a_1, a_2, \ldots, a_n~. Một bước nhảy từ phần tử ~a_i~ đến phần tử ~a_j~ được gọi là bước nhảy xa nhất của dãy nếu thỏa mãn các điều kiện sau:

• 1 ≤ ~i < j~ ≤ ~N~.
• ~a_j - a_i \geq p~.
• ~j - i~ lớn nhất (Khi đó ~j - i~ được gọi là độ dài bước nhảy xa nhất của dãy).

Yêu cầu: Tìm độ dài bước nhảy xa nhất của dãy ~a~.

Input

Dòng đầu chứa hai số nguyên ~n~ và ~p~ (~1 ≤ n ≤ 10^5; 0 ≤ p ≤ 10^9~)

Dòng tiếp theo gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~0 ≤ a_i ≤ 10^9~ với ~1 ≤ i ≤ n~)

Output

Một số nguyên dương duy nhất là độ dài của bước nhảy xa nhất của dãy (Nếu không có bước nhảy nào thỏa mãn thì ghi kết quả bằng 0).

Sample Test

Input

6 3
4 3 7 2 6 4

Output

3

Trên trục tọa độ Ox, cho ~N~ điểm khác nhau ~P_1, P_2, \ldots, P_N~. Đoạn thẳng ~AB~ được gọi là đoạn thẳng chia đều nếu nó được xác định bởi 3 điểm cho trước ~A, B, M~ sao cho ~M~ là trung điểm của ~AB~.

Yêu cầu: Cho biết tọa độ của ~N~ điểm ~P_1, P_2, \ldots, P_N~. Hỏi có bao nhiêu đoạn thẳng chia đều được tạo ra từ các điểm đã cho?

Ghi chú: Các số thực trong bộ test được so sánh là bằng nhau nếu trị tuyệt đối hiệu giữa chúng ~< 10^{-10}~

Input

Dòng đầu chứa số nguyên dương ~N~

Dòng tiếp theo gồm các số ~x_1, x_2, \ldots, x_N~ (~|x_i| \le 10^5~) tương ứng là tọa độ của các điểm ~P_1, P_2, \ldots, P_N~

Output

Một số duy nhất là kết quả tìm được của bài toán.

Sample Test

Input

5
3 -1 2 5 4

Output

3

Giải thích

• Đoạn 1: ~3 -1~, trung điểm ~2~
• Đoạn 2: ~2 4~, trung điểm ~3~

Cho dãy số ~a~ có ~N~ phần tử nguyên ~a_1, a_2, \ldots, a_N~ và một số nguyên ~S~ bất kỳ. Một dãy con liên tiếp của dãy số có dạng ~a_i, a_{i+1}, \ldots, a_j~ với ~1 \le i \le j \le N~, tổng của dãy con liên tiếp ~a_i, a_{i+1}, \ldots, a_j~ là ~a_i + a_{i+1} + \ldots + a_j~, độ dài dãy con liên tiếp ~a_i, a_{i+1}, \ldots, a_j~ bằng ~j - i + 1~.

Yêu cầu: Tìm dãy con liên tiếp của dãy số ~a~ có độ dài lớn nhất và có tổng không lớn hơn ~S~.

Input

Dòng đầu ghi số nguyên ~N~ và ~S~

Dòng tiếp theo ghi lần lượt các số nguyên ~a_1, a_2, \ldots, a_N~ (~|a_i| \le 10^6~, ~i = 1 \ldots N~)

Output

Một số duy nhất là số độ dài dãy con liên tiếp thỏa mãn.

Example

Input

8 7
6 8 2 4 5 1 9 3

Output

5

Công ty Omega tổ chức chương trình quay số siêu trúng thưởng cho khách hàng nhân dịp kỷ niệm 100 năm ngày thành lập công ty. Công ty có một bảng điện tử gồm ~n~ ô được đánh số từ 1 đến ~n~, mỗi ô hiển thị một số nguyên dương. Người quay số được quay ~m~ lần, mỗi lần quay được một số nguyên dương khi đó trên bảng điện tử các ô có số trùng với số của mỗi lần quay sẽ bị xóa. Sau mỗi lần quay, tiền thưởng của khách hàng là tổng lớn nhất của một loại số trong các số còn hiển thị trên bảng điện tử. Em hãy đóng vai là người quay số đó và thử vận may của mình nhé.

Yêu cầu: Hãy cho biết các số còn hiển thị trên bảng điện tử và tổng số tiền thưởng của mình là bao nhiêu?

Input

Dòng 1: ghi 2 số nguyên dương ~n~ và ~m~ (~n, m \le 3 \times 10^6~)
Dòng 2: ghi ~n~ số nguyên dương ~A_1, A_2, \ldots, A_n~ (~A_i \le 10^9~, với ~i = 1 \ldots n~) là các số trên bảng điện tử
Dòng 3: ghi ~m~ số nguyên dương ~B_1, B_2, \ldots, B_m~ (~B_j \le 10^9~, với ~j = 1 \ldots m~) là các số sau mỗi lần quay

Output

Dòng 1: ghi các số còn hiển thị trên bảng điện tử sau m lần quay theo thứ tự ban đầu
Dòng 2: ghi tổng tiền thưởng nhiều nhất có thể được. Nếu các số trên bảng điện tử bị xóa hết, thì đưa ra số 0.

Sample Test

Input 1

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

Output 1

7 5 2 5 7 5
16

Input 2

8 5
1 7 5 2 5 7 5 1
3 1 4 2 4

Output 2

7 5 7 5 1
16

Cho một dãy số nguyên dương ~a_1, a_2, \ldots, a_n~ (~10 < N < 100.000~, ~a_i \le 10.000~ với mọi ~i = 1 \ldots N~) và một số nguyên dương ~S~ (~S < 100.000.000~).

Yêu cầu: Tìm độ dài nhỏ nhất của dãy con chứa các phần tử liên tiếp của dãy mà có tổng các phần tử lớn hơn hoặc bằng ~S~.

Input

Dòng 1: ghi 2 số ~N~ và ~S~ ở dòng đầu
Dòng 2: chứa các phần tử của dãy.

Output

Một số duy nhất là độ dài của dãy con tìm được.

Sample Test

Input

10 15
5 1 3 5 10 7 4 9 2 8

Output

2

Nhảy lò cò là trò chơi dân gian của Việt Nam. Người trên hành tinh X cũng rất thích trò chơi này và họ đã cải biến trò chơi này như sau: trên mặt phẳng vẽ ~n~ vòng tròn được đánh số từ ~1~ đến ~n~. Tại vòng tròn ~i~ người ta điền số nguyên dương ~a_i~: hai số trên hai vòng tròn tùy ý không phân biệt nhất thiết phải khác nhau. Tiếp đến người ta vẽ các mũi tên là: nếu có ba số ~a_i, a_j, a_k~ thỏa mãn ~a_k = a_i + a_j~ thì vẽ mũi tên hướng từ vòng tròn ~i~ đến vòng tròn ~k~ và mũi tên hướng từ vòng tròn ~j~ đến vòng tròn ~k~. Người chơi chỉ được di chuyển từ một vòng tròn đến một vòng tròn khác nếu có mũi tên xuất phát từ một trong số các vòng tròn, di chuyển theo cách mũi tên đã vẽ để đi đến các vòng tròn khác. Người thắng cuộc sẽ là người tìm được cách di chuyển qua nhiều vòng tròn nhất.

Ví dụ: Với ~5~ vòng tròn và các số trong vòng tròn là ~1, 2, 6, 4, 3~, trò chơi được trình bày trong hình dưới đây:

Khi đó có thể di chuyển được nhiều nhất qua ~4~ vòng tròn (tương ứng với đường di chuyển được tô đậm trên hình vẽ).

Yêu cầu: Hãy xác định xem trong trò chơi mô tả ở trên nhiều nhất có thể di chuyển qua bao nhiêu vòng tròn?

Input

Dòng đầu chứa số nguyên n (~3 ≤ n ≤ 1000~).
Dòng thứ hai chứa dãy số nguyên dương ~a_1, a_2, \ldots, a_n~ (~a_i \le 10^9~, với ~i = 1 \ldots n~). Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra một số nguyên là số lượng vòng tròn lớn nhất tìm được.

Sample Test

Input

5
1 2 6 4 3

Output

4

Ràng buộc

~60\%~ tests ứng với ~60\%~ số điểm của bài có ~3 ≤ n ≤ 100~.

Trong khu vườn, người ta trồng một hàng cây chạy dài gồm có ~N~ cây, mỗi cây có độ cao là ~a_1, a_2, \ldots, a_N~. Người ta cần lấy ~M~ mét gỗ bằng cách đặt cưa máy sao cho lưỡi cưa ở độ cao ~H~ (mét) để cưa tất cả các cây có độ cao lớn hơn ~H~ (dĩ nhiên những cây có độ cao không lớn hơn ~H~ thì không bị cưa).

Ví dụ: Nếu hàng cây có các cây với độ cao tương ứng là ~20, 15, 10~ và ~18~ mét, cần lấy ~7~ mét gỗ. Lưỡi cưa đặt tại độ cao hợp lí là ~15~ mét thì độ cao của các cây còn lại sau khi bị cưa tương ứng là ~15, 15, 10~ và ~15~ mét. Tổng số mét gỗ lấy được là ~8~ mét (dư ~1~ mét).

Yêu cầu: Hãy tìm vị trí đặt lưỡi cưa hợp lí (số nguyên ~H~ lớn nhất) sao cho lấy được ~M~ mét gỗ và số mét gỗ dư ra là ít nhất.

Input

Dòng thứ nhất chứa ~2~ số nguyên dương ~N~ và ~M~ (~1 ≤ N ≤ 10^6; 1 ≤ M ≤ 2 \times 10^9~) cách nhau một dấu cách.

Dòng thứ hai chứa ~N~ số nguyên dương ~a~ là độ cao của mỗi cây trong hàng (~1 ≤ a_i ≤ 10^9~, với ~i = 1 \ldots N~), mỗi số cách nhau ít nhất một dấu cách.

Output

Một số nguyên là giá trị cần tìm.

Sample Test

Input

4 7
20 15 10 18

Output

15

Cho số nguyên ~n~ ~(2 ≤ n ≤ 2^{31} - 1)~. Hãy xác định số lượng số nguyên tố cùng nhau với ~n~ và nhỏ hơn ~n~.

Input

Một dòng duy nhất chứa số nguyên ~n~.

Output

Một số nguyên duy nhất là kết quả bài toán.

Sample Test

Input

7

Output

6

Cho ~N~ số nguyên tố và một số nguyên ~M~. Cho biết có bao nhiêu số trong đoạn ~[1, M]~ chia hết cho một trong ~N~ số nguyên tố đã cho.

Input

Dòng đầu tiên ghi hai số nguyên dương ~n, m~ (~1 ≤ n ≤ 20, 1 ≤ m ≤ 10^9~)

Dòng thứ hai ghi ~n~ số nguyên tố

Output

Ghi ra một số duy nhất là kết quả bài toán.

Sample Test

Input

4 200
2 5 7 11

Output

137

Một bài toán về số học thú vị như sau: "Một số hoàn hảo là một số không vượt quá 100 chỉ gồm các chữ số 4, 6 và 9. Một số được gọi là số đẹp nếu nó chia hết cho ít nhất một số hoàn hảo nào đó. Cho số tự nhiên ~n~ (~1 ≤ n ≤ 18~), tìm số lượng số đẹp không vượt quá ~10^n~ ".

Input

Dòng đầu tiên chứa số nguyên dương ~T~ (~1 ≤ T ≤ 10~) là số lượng bài toán cần giải.

~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ tương ứng với yêu cầu bài toán (~1 ≤ n ≤ 18~).

Output

Gồm ~T~ dòng, mỗi dòng chứa kết quả bài toán ứng với bài toán cần giải.

Sample Test

Input

1
1

Output

5

Nhằm tri ân khách hàng đã tin tưởng và luôn ủng hộ các loại sản phẩm của cửa hàng. Cửa hàng có ~n~ phần quà khuyến mãi đánh số từ 1 tới ~n~ và một kế hoạch trao tặng khách hàng khá thú vị: Khách hàng thứ ~i~ vào mua hàng sẽ được tặng hết các phần quà khuyến mãi còn lại có số hiệu chia hết cho ~i + 1~. Trong khi xếp hàng đợi vào mua, An thấy mình đứng ở số thứ tự ~k~. An muốn nhẩm tính xem mình có thể may mắn được tặng bao nhiêu phần quà từ cửa hàng này.

Input

Một dòng chứa số nguyên dương ~n~ và ~k~ (~1 ≤ n, k ≤ 2 \times 10^9~).

Output

Một số nguyên duy nhất là số quà mà An được tặng.

Sample Test

Input

3 2

Output

1

Nhà trường quyết định xây dựng riêng cho mình một mạng xã hội để các bạn trẻ có điều kiện giao lưu một cách tốt nhất. Hệ thống sẽ tự động chọn và giới thiệu cho mỗi người những người bạn tiềm năng trong trường. Khi đăng ký, người tham gia sẽ phải trải qua thủ tục trắc nghiệm tâm lý. Kết quả trắc nghiệm cho biết giá trị tâm lý theo ba chỉ số, mỗi giá trị là một số nguyên dương. Thực tế cuộc sống cho thấy, nếu 2 người có giá trị khác nhau ở cả 3 chỉ số thì họ sẽ thường xuyên rơi vào tranh luận, cãi nhau bất tận, còn nếu có giá trị ở 2 hay 3 chỉ số trùng nhau thì mối quan hệ, nếu có – sẽ rất buồn chán. Như vậy, để có một mối quan hệ có lợi và duy trì được lâu dài thì hai người phải có cùng giá trị ở một chỉ số nào đó, còn giá trị ở các chỉ số còn lại phải khác nhau. Với ~n~ nhóm ba (~a_i, b_i, c_i~) hãy cho biết có bao nhiêu cặp ~i < j~ mà số lượng đẳng thức ~a_i = a_j, b_i = b_j, c_i = c_j~ chỉ có đúng một.

Input

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

Dòng thứ ~i~ trong ~n~ dòng sau chứa 3 số nguyên ~a_i, b_i, c_i~ (~1 ≤ a_i, b_i, c_i ≤ 100~)

Output

Một số nguyên duy nhất là số lượng cặp tìm được.

Sample Test

Input

4
100 100 100
99 100 100
100 99 100
99 99 99

Output

5

Ở đầu ra của một dây chuyền sản xuất trong nhà máy ZXY có một máy xếp tự động. Sau khi kết thúc việc gia công trên dây chuyền, các sản phẩm sẽ được xếp vào các hộp có cùng dung lượng ~M~. Sản phẩm rời khỏi dây chuyền được xếp vào hộp đang mở (khi bắt đầu ca làm việc có một hộp rỗng được mở sẵn) nếu như dung lượng của hộp còn đủ để chứa sản phẩm. Trong trường hợp ngược lại, máy sẽ tự động đóng nắp hộp hiện tại, cho xuất xưởng rồi mở một hộp rỗng mới để xếp sản phẩm vào. Trong một ca làm việc có n sản phẩm đánh số từ ~1~ đến ~n~ theo thứ tự mà chúng rời khỏi dây chuyền. Sản phẩm thứ ~i~ có trọng lượng là ~a_i~, ~i = 1, 2, ..., n~. Ban Giám đốc nhà máy đề nghị sản phẩm xuất xưởng của mỗi ca làm việc phải được xếp vào trong không quá ~k~ hộp.

Yêu cầu: Hãy giúp người quản đốc của ca làm việc xác định giá trị M nhỏ nhất sao cho số hộp mà máy tự động cần sử dụng để xếp đầy n sản phẩm xuất xưởng của ca không vượt quá k cho trước.

Input

Dòng đầu tiên chứa hai số nguyên n và k (~1 ≤ k ≤ n ≤ 10^5~)

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa số nguyên dương ~a_i~ (~a_i ≤ 30,000~ với ~i = 1, 2, ..., n~)

Output

Một số nguyên duy nhất là dung lượng của hộp.

Sample Test

Input

9 4
1
1
1
3
2
2
1
3
1

Output

5

Trên mặt biển có ~n~ hòn đảo. Có thể xem mặt biển là một mặt phẳng còn các hòn đảo là các điểm nằm tại các tọa độ ~(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)~, nghĩa là đảo thứ ~i~ cách gốc tọa độ ~x_i~ mét theo trục hoành, ~y_i~ mét theo trục tung. Ban đầu mỗi hòn đảo là một hình vuông có chiều dài cạnh là ~2~ mét (tâm hình vuông là tọa độ các hòn đảo). Sau đó mỗi tháng tùy theo lượng phù sa nhiều hay ít mà mỗi hòn đảo được bồi đắp mở rộng cả bốn hướng mỗi hướng thêm ~1~ mét (phù sa ít) hay ~2~ mét (phù sa nhiều) để tạo thành hình vuông lớn hơn. Trong một tháng các hòn đảo đều được bồi đắp giống nhau (cùng ~1~ mét hoặc cùng ~2~ mét).

Giả sử nếu quá trình bồi đắp xảy ra trong ~k~ tháng, bạn hãy tính xem có sự va chạm giữa các hòn đảo hay không (ít nhất ~2~ đảo chạm nhau) và sự va chạm đó xảy ra vào tháng nào. (Nếu sau một tháng nào đó, cạnh hai đảo chỉ mới chạm mép vào nhau, hoặc ~2~ đỉnh chạm nhau thì cũng xem như tháng đó xảy ra sự va chạm).

Yêu cầu: Hãy xác định xem trong quá trình bồi đắp có sự va chạm giữa các hòn đảo hay không, nếu có thì xảy ra vào tháng nào.

Input

Dòng thứ nhất gồm 2 số nguyên ~n~, ~k~ là số hòn đảo và số tháng bồi đắp, hai số cách nhau một khoảng trắng (~2 ≤ n ≤ 200~, ~1 ≤ k ≤ 100.000~)

Trong ~n~ dòng tiếp theo, tại dòng thứ ~i~ gồm ~2~ số ~x_i~ và ~y_i~ là tọa độ các hòn đảo, hai số cách nhau một khoảng trắng (~-10^9 ≤ x_i, y_i ≤ 10^9~)

Dòng tiếp theo là một dãy ~k~ ký tự ứng với ~k~ tháng bồi đắp, nếu đó là ký tự '1' thì tháng đó mở rộng ~1~ mét, nếu đó là ký tự '2' thì tháng đó mở rộng ~2~ mét, ngoài ra không có ký tự khác.

Output

Một số nguyên duy nhất là tháng mà sau khi bồi đắp thì bắt đầu xảy ra va chạm, nếu không có va chạm thì in ra ~-1~.

Sample Test

Input 1

2 4
1 0
7 0
1122

Output 1

2

Input 2

2 5
1 1
13 13
21112

Output 2

4

Input 3

2 7
1 0
100 1
1121122

Output 3

-1

Một đoạn số có tổng bằng nhau trong một dãy số là một nhóm các số theo đúng thứ tự ban đầu trong dãy mà nếu nhóm với nhau thì sẽ cho ra cùng một giá trị tổng. Ví dụ với dãy: ~2 5 1 3 3 7~ thì ta có thể nhóm thành: ~(2 5) (1 3 3) (7)~ cùng cho giá trị tổng là ~7~.

Chú ý: đoạn đặc biệt chứa tất cả các phần tử của dãy cũng được coi là một đoạn có tổng bằng nhau với chính giá trị tổng các số của dãy đó.

Yêu cầu: Viết chương trình nhận vào các dãy số nguyên dương và trả về giá trị tổng nhỏ nhất có thể của một đoạn tổng bằng nhau trong dãy.

Input

Dòng đầu tiên chứa một số nguyên ~1 ≤ t ≤ 1000~ là số lượng bộ test. Mỗi bộ test bao gồm:

• Dòng đầu tiên chứa thứ tự bộ test và số ~M~ (~1 ≤ M ≤ 10000~) là số phần tử của dãy.
• Các dòng tiếp theo mỗi dòng ghi ~10~ số của dãy phân cách bởi ~1~ dấu cách. Dòng cuối cùng có thể có ít hơn ~10~ số. (Các số trong dãy đều nhỏ hơn ~20000~).

Output

Với mỗi bộ test, in ra trên một dòng gồm số thứ tự bộ test và tổng nhỏ nhất có thể đạt được của các đoạn số có tổng bằng nhau.

Sample Test

Input

3
1 6
2 5 1 3 3 7
2 6
1 2 3 4 5 6
3 20
1 1 2 1 2 1 1 2 1 2 1 1 1 2 1 1 1 2 1 1

Output

1 7
2 21
3 2

Sau khi thực thi quy hoạch của Bộ Giao thông, sơ đồ giao thông của thành phố H gồm ~n~ tuyến đường ngang và ~n~ tuyến đường dọc cắt nhau tạo thành một lưới ô vuông với ~n \times n~ nút giao thông. Các nút giao thông được gán tọa độ theo hàng từ ~1~ đến ~n~, từ trên xuống dưới và theo cột từ ~1~ đến ~n~, từ trái sang phải. Ban chỉ đạo an toàn giao thông quyết định điều ~n~ cảnh sát giao thông đến các nút giao thông làm nhiệm vụ. Ban đầu mỗi cảnh sát được phân công đứng trên một nút của một tuyến đường ngang khác nhau. Đến giờ cao điểm, xuất hiện ùn tắc tại các tuyến đường dọc không có cảnh sát giao thông. Để sớm giải quyết tình trạng này, Ban chỉ đạo an toàn giao thông quyết định điều động một số cảnh sát giao thông ở một số nút, từ nút hiện tại sang một nút khác cùng hàng ngang để đảm bảo mỗi tuyến đường dọc đều có mặt của cảnh sát giao thông.

Yêu cầu: Biết rằng cảnh sát ở hàng ngang thứ ~i~ cần ~t_i~ đơn vị thời gian để di chuyển qua ~1~ cạnh của lưới ô vuông (~i = 1, 2, \ldots, n~), hãy giúp Ban chỉ đạo an toàn giao thông tìm cách điều động các cảnh sát thỏa mãn yêu cầu đặt ra sao cho việc điều động được hoàn thành tại thời điểm sớm nhất. Giả thiết là các cảnh sát được điều động đồng thời thực hiện việc di chuyển đến vị trí mới tại thời điểm ~0~.

Input

Dòng thứ nhất chứa một số nguyên dương ~n~ (~n ≤ 10000~)

Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa hai số nguyên dương ~c_i~, ~t_i~ (~t_i ≤ 10000~) tương ứng là tọa độ cột và thời gian để di chuyển qua ~1~ cạnh của lưới ô vuông của cảnh sát đứng trên tuyến đường ngang thứ ~i~ (~i = 1, 2, \ldots, n~).
Hai số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách

Output

Một số nguyên duy nhất là thời điểm sớm nhất tìm được.

Sample Test

Input

5
5 10
3 10
3 20
2 9
2 15

Output

10

Ràng buộc:

~50\%~ số tests ứng với ~50\%~ số điểm của bài có ~n ≤ 100~.