Cho dãy số nguyên ~a~ gồm ~n~ phần tử. Hãy tìm cách chia dãy ~a~ ra thành ít dãy con (không nhất thiết liên tiếp) nhất, sao cho các dãy con đều là dãy không giảm và mỗi phần tử của ~a~ thuộc đúng một dãy con.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(n \le 10^5)~

• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~a~. (~a_i \le 10^9~)

  Output

• In ra số lượng dãy con ít nhất thỏa mãn.

Sample Test

Input:

4
1 5 4 6

Output:

2

Cho 2 dãy số nguyên dương ~a~ có ~n~ phần tử và ~b~ có ~m~ phần tử. Với ~j~ từ 1 đến ~m~ hãy tìm ~gcd(a_1 + b_j, a_2 + b_j,...,a_n + b_j)~.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~1 \le n, m \le 2 \times 10^5~.
• Dòng thứ 2 gồm ~n~ số nguyên dương ~1 \le a_i \le 10^9~.
• Dong thứ 3 gồm ~n~ số nguyên dương ~1 \le b_j \le 10^9~.

Output

• In ra ~m~ số nguyên tương ứng với đáp án.

Sample Test

Input:

4 4
1 25 121 169
1 2 7 23

Output:

2 3 8 24

Do đã quá quen với dãy fibonacci, hôm nay, chúng ta hãy cùng tìm hiểu về dãy tribonacci.

Số tribonacci thứ ~i~ sẽ có công thức truy hồi như sau: ~f[i] = f[i-1] + f[i-2] + f[i-3]~ nếu ~i > 3~, ngược lại ~f[i] = i~ nếu ~i \le 3~.

Cho ~n~ số tribonacci đầu tiên và một số ~k~ (~k \le n~), hay tìm một dãy con bất kì (không nhất thiết phải liên tiếp) của dãy ~n~ số tribonacci này sao cho tổng của các phần tử trong dãy con đó chia hết cho ~k~.

Input

• Gồm một dòng chứa số nguyên dương ~n~ và số nguyên dương ~k~ ~(1 \le k \le n \le 10^5)~

Output

• Dòng đầu in ra số ~q~ là độ dài của dãy con thỏa mãn tìm được, nếu không tồn tại in ra ~-1~.
• Dòng thứ hai in ra ~q~ chỉ số của dãy con tìm được.
• Nếu có nhiều hơn một dãy con thỏa mãn, in ra bất kì kết quả nào.

Subtask

• ~30\%~ số test có ~n \le 20~.
• ~40\%~ số test có ~n \le 2000~.
• ~30\%~ số test còn lại có ~n \le 10^5~.

Sample Test

Input:

5 4

Output:

2
2 4

Giải thích:

• ~5~ phần tử đầu tiên của dãy tribonacci là: 1 2 3 6 11

• Chọn ra phần tử thứ ~2~ và ~4~ có tổng bằng: ~2+6 = 8~ chia hết cho ~4~.

Hôm nay Sủi shop được ~n~ bài để cho vào chên ninh contest. Mỗi bài có 2 chỉ số ~a_i~ là chủ đề của bài và ~b_i~ là độ khó, tất cả các bài đều khác nhau, nghĩa là không có 2 bài bất kì nào đều có cùng chủ đề và độ khó. Sủi cần chọn ra 3 bài thỏa mãn ít nhất 1 trong 2 điều kiện sau:

• Chủ đề của 3 bài khác nhau.
• Độ khó của 3 bài khác nhau.

Hãy đếm số cách để Sủi có thể chọn ra 3 bài như vậy.

Input

• Dòng đầu tiên gồm số nguyên không âm ~3 \le n \le 10^5~.
• ~n~ dòng tiếp theo mỗi dòng gồm 2 số ~1 \le a_i, b_i \le n~.

Output

• Hãy in ra số cách chọn.

Sample Test

Input:

4
2 4
3 4
2 1
1 3

Output:

3

Input:

5
1 5
2 4
3 3
4 2
5 1

Output:

10

Cho 2 số nguyên không âm ~n, m~, hãy tìm MEX của dãy ~[n \oplus 0, n \oplus 1,..., n \oplus m]~.

MEX của một dãy số nguyên không âm là số nguyên không âm nhỏ nhất không xuất hiện trong dãy này.

Input

• Dòng đầu tiên gồm số lượng test ~t~.
• ~t~ dòng sau mỗi dòng gồm 2 số ~n~ và ~m~.

Output

• In ra ~t~ dòng lần lượt là đáp án của từng test.

Sample Test

Input:

5
3 5
4 6
3 2
69 696
123456 654321

Output:

4
3
0
640
530866