Từ dãy số tự nhiên ~1; 2; 3; ...; N~ người ta sắp xêp lại dãy số này theo số dư trong các phép chia các số hạng của dãy số cho một số lự nhiên ~K~ là ước nào đó của ~N~ như sau:

• Đoạn thứ nhất gồm tất cả các số chia hết cho ~K~;
• Đoạn thứ hai gồm tất cả các sổ chia ~K~ dư 1;
• Đoạn thứ ba gồm tất cả các số chia ~K~ dư 2;
• ...
• Đoạn cuối cùng gồm tất cà các số chia ~K~ dư ~K~ - 1.

Các số hạng trong mỗi đoạn cũng được sắp xếp theo chiêu tăng dần.

Ví dụ: Với ~N = 12~ và ~K = 4~ sau khi sắp xếp ta có dãy số sau: ~4; 8; 12; 1; 5; 9; 2; 6; 10; 3; 7; 11~

Yêu cầu: Cho trước 3 số nguyên dương ~N; K; M~ (với ~K~ là ước của ~N~ và ~M < N~). Tìm số hạng thử ~M~ của dãy đã sắp xếp.

Input

• 3 số nguyên dương ~N; K; M~ (~N \le 10^{16}; K \le 10^9; K~ là ước của ~N~; ~M < N~) trên cùng một dòng, mỗi số cách nhau một dấu cách.

Output

• Ghi ra số hạng thứ M của dãy số theo yêu cầu.

Scoring

• Có 20% test ứng với ~N \le 10^2~;
• Có 30% test ứng với ~10^2 < N \le 10^6~;
• Có 30% test ứng với ~10^6 < N \le 10^9~;
• Có 20% test ứng với ~10^9 < N \le 10^{16}~.

Sample Tests

Input

12 4 6

Output

9

Cho hai dãy ~a~ và ~b~ gồm ~n~ phần tử nguyên dương. Bạn được nhận thêm một số nguyên dương ~k~, hãy đếm số cặp ~(i,j)~ ~(1 \le i,j \le n)~ sao cho ~\overline{a_ib_j}~ ~\vdots~ ~k~.

Nói cách khác, hãy đếm số cặp ~(i,j)~ sao cho số nguyên dương ~X~ được tạo bởi cách viết liền ~a_i~ và ~b_j~ với nhau chia hết cho số nguyên dương ~K~ cho trước.

Ví dụ:

• ~a_i = 5, b_j = 77 \Rightarrow X = 577~
• ~a_i = 66, b_j = 99 \Rightarrow X = 6699~

Input

• Dòng đầu tiên gồm số hai nguyên dương ~n~ và ~k~ ~(1 \le n,k \le 3 \times 10^5)~
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~ ~(1 \le a_i \le 3 \times 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~b_1,b_2,...,b_n~ ~(1 \le b_i \le 3 \times 10^5)~.

Output:

• Gồm một dòng in ra số cặp ~(i,j)~ thỏa mãn.

Subtask:

• Subtask ~1~ (~40\%~ số điểm): ~n \le 2000~.
• Subtask ~2~ (~30\%~ số điểm): ~a_i,b_j \le 2000~ ~\forall i,j \in [1,n]~.
• Subtask ~3~ (~30\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

4 3
1 4 3 6
11 2 4 21 

Sample Output 1

6

Explanation 1

Có các cặp sau:

• ~(1,1) = 111~
• ~(1,2) = 12~
• ~(2,1) = 411~
• ~(2,2) = 42~
• ~(3,4) = 321~
• ~(4,4) = 621~

Bạn được cho một mảng ~a~ gồm ~n~ phần tử nguyên dương phân biệt. Ở mỗi bước, bạn có thể chọn ra một số nguyên dương ~x~, sao cho ~x~ không xuất hiện trong dãy ~a~, sau đó thêm số ~x~ vào đuôi của ~a~.

Để tránh biến đây thành một chuỗi hành động dài vô tận, bạn quyết định sẽ dừng lại khi tổng của các phần tử trong dãy ~a~ lớn hơn hoặc bằng giá trị ~k~ cho trước.

Bạn muốn chơi trò chơi này lâu nhất có thể (hơi ngược đời nhỉ), vậy nên hãy tìm ra chiến thuật tốt nhất để chơi được nhiều lượt nhất!

Input

• Dòng đầu chứa hai số nguyên dương ~n,k~ miêu tả độ dài của dãy ~a~ ban đầu và số ~k~ cho trước ~(1 \le n \le 2 \times 10^5, 1 \le k \le 10^{18})~.
• Dòng thứ hai chứa ~n~ số nguyên dương phân biệt ~a_1,a_2,...,a_n~ ~(1 \le a_i \le 10^{12})~.

Output

• Gồm một số nguyên dương là số lượt chơi lâu nhất có thể nếu bạn chơi tối ưu.

Subtask

• Subtask ~1~ (~15\%~ số điểm): ~n \le 100, k \le 10^6~
• Subtask ~2~ (~25\%~ số điểm): ~n \le 1000, k \le 10^9~
• Subtask ~3~ (~30\%~ số điểm): ~n \le 10^5, k \le 10^{12}~
• Subtask ~5~ (~30\%~ số điểm): Không có ràng buộc gì thêm

Sample input 1

3 15
1 3 5

Sample output 1

2

Sample input 2

5 35
1 4 2 6 12

Sample output 2

3

Explanation:

• Ở ví dụ thứ nhất, bạn chỉ có thể chơi ~2~ lượt, giả sử bạn lần lượt thêm vào ~2~, dãy sau đó trở thành ~[1,3,5,2]~, và ở lượt sau bạn thêm vào ~4~, dãy trở thành ~[1,3,5,2,4]~. Lúc này dãy đã vừa đủ có tổng bằng ~k=15~ nên sẽ không được thêm nữa.

Bạn được cho một mảng ~a~ gồm ~n~ số nguyên dương, đánh số từ ~1~ đến ~n~. Hãy gọi một mảng là đầy đủ nếu với mọi cặp giá trị ~x~ và ~y~ trong mảng (biết ~x~ và ~y~ không nhất thiết phải khác nhau), với điều kiện ~x \geq y~, thì số ~\left \lfloor \frac{x}{y} \right \rfloor~ (lấy ~x~ chia cho ~y~ rồi làm tròn xuống) cũng phải nằm trong mảng.

Bạn được đảm bảo rằng tất cả các số trong mảng ~a~ đều không vượt quá ~c~. Nhiệm vụ của bạn là kiểm tra xem mảng này có phải là đầy đủ hay không.

Bạn sẽ phải trả lời nhiều truy vấn.

Input

• Dòng đầu tiên gồm một số nguyên dương ~t~ ~(1 \le t \le 10^4)~ là số truy vấn, mỗi truy vấn sẽ có dạng như sau:
  • Dòng đầu chứa hai số nguyên dương ~n,c~ mô tả dãy ~a~ ban đầu và cận trên của các giá trị ~a_i~ trong dãy ~(1 \le n \le 2 \times 10^5, 1 \le C \le 10^7)~.
  • Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,...,a_n~ ~(1 \le a_i \le c)~.
• Gọi ~N~ là tổng ~n~ của các truy vấn, tương tự ~C~ là tổng ~c~ của các truy vấn, dữ liệu đảm bảo ~N \le 10^6~ và ~C \le 10^7~.

Output

• Với mỗi truy vấn, in ra "Yes" (không có dấu ngoặc) nếu dãy đó là dãy đầy đủ, ngược lại in ra "No".

Subtask

• Subtask ~1~ (~10\%~ số điểm): ~N \le 100, C \le 10^7~
• Subtask ~2~ (~20\%~ số điểm): ~N \le 10^5, C \le 10^4~
• Subtask ~3~ (~20\%~ số điểm): ~N \le 1000~
• Subtask ~4~ (~30\%~ số điểm): ~N \le 10^5~
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm

Sample input 1

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

Sample output 1

Yes
No
No