Bạn có ~N~ đồng xu và bạn muốn xây cầu thang bằng những đồng xu này. Cầu thang gồm k hàng, hàng thứ ~i~ có đúng ~i~ đồng xu. Hàng cuối cùng của cầu thang có thể không đầy đủ do thiếu xu.

Yêu cầu: cho số nguyên ~N~, trả về số hàng hoàn chỉnh của cầu thang bạn sẽ xây dựng được.

Dữ liệu vào: Đọc ở file văn bản STAIR.INP một số N (~1 ≤ N ≤ 10^9~) là số đồng xu.

Dữ liệu ra: Ghi ra file văn bản STAIR.OUT một số nguyên dương duy nhất là số hàng hoàn chỉnh của cầu thang.

Ví dụ:

STAIR.INP

5

STAIR.OUT

2

GIẢI THÍCH: Vì hàng thứ 3 chưa được hoàn thành nên có 2 hàng hoàn chỉnh

Cho một mảng arr các số nguyên dương được sắp xếp theo thứ tự tăng dần và một số mảng kArr. Với mỗi giá trị thuộc mảng kArr, in ra số nguyên dương thứ kArr bị thiếu trong mảng arr.

Dữ liệu vào: Đọc ở file văn bản KTH.INP:

Dòng đầu chứ số nguyên dương ~N~ và K lần lượt là số phần tử của mảng arr và mảng kArr.

~N~ dòng tiếp theo mỗi dòng chứa giá trị ~arr_i~ (Mỗi giá trị ~arr_i~ là khác nhau).

~K~ dòng tiếp theo mỗi dòng chứa giá trị ~kArr_i~.

Dữ liệu ra: Ghi ra file văn bản KTH.OUT gồm ~K~ dòng, mỗi dòng là số nguyên dương bị thiếu thỏa đề bài.

Giới hạn: ~1≤N≤10^5~; ~1≤K≤10^3~; ~1≤arr_i, kArr_i≤ 10^5~

Ví dụ:

KTH.INP

5 1
2
3
4
7
11
5

KTH.OUT

9

*Giải thích: *

Các số nguyên dương còn thiếu là [1,5,6,8,9,10,12,13,...]. Số nguyên dương còn thiếu thứ 5 là 9.

"Trick or Treat" - "Cho kẹo hay bị ghẹo", một phong tục không thể thiếu và cũng là hoạt động được trẻ em mong chờ nhất trong dịp Halloween. Trẻ em được hóa trang thành siêu nhân, công chúa hay các nhân vật kinh dị, rồi đi xin kẹo trong ngày Halloween.

Buổi tối Halloween, ~K~ đứa trẻ đã đến gõ cửa xin kẹo nhà ông Phú. Ông Phú đã chuẩn bị ~N~ gói kẹo, mỗi gói có chứa ~a_i~ viên kẹo. Ông cần phải lấy một số gói kẹo cho ~K~ đứa trẻ sao cho tổng số viên kẹo có thể chia đều cho ~K~ đứa. Bạn hãy tính xem có bao nhiêu cách lấy số gói kẹo thỏa mãn.

Dữ liệu vào: Đọc ở file văn bản TRICK.INP:

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

Dòng tiếp theo chứa N số nguyên dương ~a_i~ tương ứng số kẹo trong gói kẹo thứ ~i~.

Dữ liệu ra: Ghi ra file văn bản TRICK.OUT một số duy nhất là số cách cần tìm sau khi chia lấy dư cho ~10^9+7~.

Giới hạn: ~1≤N≤10^3; 1≤K≤10^4 1≤a_i≤ 10^6~

Ví dụ:

TRICK.INP

4 5   
2 
1 
3 
2

TRICK.OUT

3

Giải thích:

Có 3 cách chọn {2,3}; {3,2} và {2,1,2}