Passwifi sắp tới của đội tuyển Tin Ams sẽ là ~XY~. Với ~X, Y~ là thỏa mãn:

• ~X*Y+X+Y=N^2~
• ~X \le Y~
• ~X + Y~ lớn nhất

Input

Gồm nhiều bộ test có cấu trúc như sau:

• Dòng đầu tiên ghi số nguyên dương ~Q~ là số lượng bộ test;
• ~Q~ dòng tiếp theo, mỗi dòng chứa mộ số nguyên dương ~N~ ~(N \le 10^6)~

Output

In ra ~Q~ dòng, mỗi dòng là một chuỗi ghép của hai số ~X~ và ~Y~ là kết quả của bộ test tương ứng.

Dữ liệu đảm bảo luôn có kết quả.

Subtask

• ~70\%~ số điểm: ~Q = 1~;
• ~30\%~ số điểm: ~Q \le 2500~;

Ví dụ

Input:

2
7
8

Output:

124
412

Cho dãy số nguyên ~a~ gồm ~n~ phần tử và dãy số nguyên ~b~ gồm ~m~ phần tử. Hỏi tìm cách thay các phần tử của dãy ~b~ vào dãy ~a~ sao cho dãy ~a~ có số lượng số khác nhau là ít nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, m~ mô tả số lượng phần tử của hai dãy số;
• Dòng thứ hai gồm ~n~ số nguyên mô tả dãy ~a~ ~(1 \le a_i \le 10^9)~;
• Dòng thứ ba gồm ~m~ số nguyên mô tả dãy ~b~ ~(1 \le b_i \le 10^9)~.

Output

• In ra số lượng phần tử khác nhau nhỏ nhất của dãy ~a~ sau khi thay thế (có thể không thay thế).

Subtask

• ~40\%~ số điểm: ~n \le 1000; M = 1~;
• ~30\%~ số điểm: ~n, m \le 1000~;
• ~30\%~ số điểm: ~n, m \le 10^5~.

Ví dụ

Input 1:

3 2
1 1 1
4 3

Output 1:

1

Input 2:

9 4
1 2 5 4 8 9 3 5 5
2 5 5 5

Output 2:

3

Cho một dãy ~a~ gồm ~n~ phần tử nguyên dương và một số nguyên dương ~k~.

Ta có định nghĩa như sau:

• ~MaxSecond(l,r) :~ phần tử lớn thứ hai trong đoạn ~[l,r]~ của dãy ~a~.
• ~MinSecond(l,r) :~ phần tử nhỏ thứ hai trong đoạn ~[l,r]~ của dãy ~a~.
• ~f(l,r) = MaxSecond(l,r) - MinSecond(l,r)~

Hãy tìm một đoạn con ~[l,r]~ dài nhất sao cho ~f(l,r) \le k~.

Input

• Dòng thứ nhất chứa ~2~ số nguyên dương: ~n,k~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~.

Output

• In ra số ~X~ là độ dài của đoạn con dài nhất thỏa mãn. Dữ liệu đảm bảo luôn tồn tại kết quả.

Constraints

• ~1 \le n \le 10^5~.
• ~1 \le a_i \le 10^9~.
• ~1 \le k \le 10^9~.

Subtasks

• Subtask ~1~: ~n \le 1000~ ~(50\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(50\%)~

Sample Input 1:

5 2
1 4 2 6 5

Sample Output 1:

4

Explanation 1:

Chọn đoạn ~[1,4]~.

Sample Input 2:

7 3
9 1 4 3 12 16 8

Sample Output 2:

4

Explanation 2:

Chọn đoạn ~[2,5]~.

Cho đồ thị vô hướng có trọng số gồm ~n~ đỉnh và ~m~ cạnh không chứa khuyên, mỗi cạnh có dạng ~(u,v,c)~, tức là cạnh nối hai đỉnh ~u~ và ~v~ có trọng số ~c~.

Với mỗi cạnh, hãy xác định xem cạnh đó có nằm trong mọi cây khung nhỏ nhất của đồ thị hay không.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, n-1 \le m \le 2*10^5)~
• ~m~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên ~u_i,v_i,w_i~ ~(1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^9)~ - lần lượt là hai đỉnh và trọng số của cạnh thứ ~i~.
• Dữ liệu đảm bảo đồ thị liên thông.

Output:

• In ra ~m~ xâu kí tự, trong đó xâu thứ ~i~ là "Yes" nếu cạnh thứ ~i~ thuộc toàn bộ các cây khung nhỏ nhất của đồ thị, "No" nếu ngược lại.

Constraints:

• Có ~10\%~ số test ứng với ~m \le 20~
• Có ~20\%~ số test ứng với ~m \le 300~
• Có ~20\%~ số test ứng với ~m \le 4000~;
• Có ~20\%~ số test ứng với trọng số của mọi cạnh phân biệt.
• ~30\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input 1

5 7
4 3 2
1 2 2
1 4 7
2 5 1
1 3 9
2 4 9
2 3 7

Output 1

Yes Yes No Yes No No No 

Dãy con của một dãy là dãy thu được bằng cách xóa đi một số phần tử của dãy ban đầu (có thể không xóa phần tử nào) và giữ nguyên thứ tự của các phần tử còn lại. Một dãy số được gọi là dãy tăng kép nếu có thể tách nó ra thành hai dãy con khác rỗng, sao cho mỗi phần tử của dãy ban đầu thuộc vào đúng dãy con đó, và các phần tử trong cùng một dãy con thì tăng nghiêm ngặt.

Cho dãy số nguyên ~a~ có ~n~ phần tử, hãy đếm số dãy con của ~a~ là dãy tăng kép.

Input

• Dòng đầu tiên gồm số nguyên ~n~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~ ~(1 \le a_i \le n)~

Output

• In ra số lượng dãy tăng kép là dãy con của ~a~, sau khi chia lấy dư cho ~1000000007~

Subtask :

• Subtask ~1~: ~n \le 20~ ~(20\%)~
• Subtask ~2~: ~n \le 200~ ~(20\%)~
• Subtask ~3~: ~n \le 2000~ và ~a_i \le 200~ ~(25\%)~
• Subtask ~4~: ~n \le 2000~ ~(35\%)~

Sample Input 1:

4
3 3 4 2

Sample Output 1:

9