Cho một bàn cờ ~n \times n~, trong đó cho trước một vài ô bị chặn. Các hàng được đánh số từ ~1~ đến ~n~, các cột được đánh số từ ~1~ đến ~n~. Dữ liệu đảm bảo mọi ô trống có thể đi đến các ô trống còn lại thông qua các ô trống kề cạnh. Nhiệm vụ của bạn là xác định xem có thể dùng các viên gạch ~2 \times 1~ để lấp đầy các ô trống không, biết rằng không thể dùng viên gạch để lấp đầy lên các ô bị chặn, các viên gạch không được đè nhau.

Input

Dòng đầu tiên gồm số nguyên dương ~t~ — số lượng testcase của bộ test này (~1 \le t \le 10^5~).

Trong mỗi testcase, gồm:

• Dòng đầu gồm hai số ~n~ và ~m~ (~2 \le n \le 5000, 0 \le m \le 25 \cdot 10^6~).

• Mỗi dòng trong ~m~ dòng tiếp theo chứa một cặp ~x_i~ ~y_i~ là tọa độ của ô bị chặn (~1 \le x_i, y_i \le n~).

Đảm bảo rằng tổng các ~n~ trong ~t~ testcase không quá ~5000~.

Output

Ứng với mỗi testcase, in ra "YES" nếu tồn tại một cách lấp đầy bàn cờ, ngược lại in ra "NO".

Scoring

Sample Input 1

3
4 0
3 2
3 3
3 3
2 3
1 1
1 2
2 2

Sample Output 1

YES
YES
NO

Cho hai số nguyên ~n~ và ~k~. Một số Bedao cơ số ~n~ được định nghĩa là một số nguyên dương có thể thu được từ tổng các lũy thừa riêng biệt của ~n~.

Ví dụ: Các số Bedao cơ số ~3~ có thể là ~9 = 3^2~, ~12 = 3^2 + 3^1~, ~37 = 3^3 + 3^2 + 3^0~. Trong khi đó, các số ~2, 5, 8, \ldots~ không phải là số Bedao cơ số ~3~.

Vậy, với hai số ~n~ và ~k~ cho trước, hãy tìm số Bedao cơ số ~n~ thứ ~k~ theo thứ tự tăng dần. Vì kết quả có thể rất lớn nên hãy in ra theo modulo ~10^9 + 7~.

Input

• Dòng đầu tiên gồm một số nguyên dương ~t~ (~1 \le t \le 2\times 10^5~) là số bộ test.

• ~t~ dòng sau, mỗi dòng gồm hai số nguyên dương ~n~ và ~k~ (~2 \le n \le 100~, ~1 \le k \le 10^{18}~).

Output

• In ra ~t~ dòng, mỗi dòng là số Bedao cơ số ~n~ thứ ~k~ trong bộ test đó.

Sample Input 1

3
2 24
3 5
5 2004

Sample Output 1

24
10
12203775

Notes

Ở ví dụ thứ nhất, mọi số đều là số Bedao cơ số ~n=2~, vậy nên số thứ 24 là 24.

Ở ví dụ thứ hai, ~6~ số Bedao cơ số ~n=3~ đầu tiên là ~{1, 3, 4, 9, 10, 13}~ nên đáp án là ~10~.

Bạn được cho một mảng hai chiều gồm ~N * M~ số nguyên dương ~a_{i, j} \ (a_{i, j} \leq 10^9)~, với ~1 \leq i \leq N~ và ~1 \leq j \leq M~. Ngoài ra, bạn cũng được cho ~N~ số nguyên dương ~w_i \ (w_i \leq 10^9)~, với ~1 \leq i \leq N~.

Nhiệm vụ của bạn là tìm hai vị trí ~i, j \ (1 \leq i < j \leq N)~, sao cho các số ~a_{i, 1}, a_{i, 2}, \dots, a_{i, m}, \ a_{i + 1, 1}, a_{i + 1, 2}, \dots, a_{i + 1, m}, \dots, \ a_{j, 1}, a_{j, 2}, \dots, a_{j, m}~ phân biệt, đồng thời ~w_i + w_j~ là nhỏ nhất, hoặc in ra ~-1~ nếu không tồn tại cặp ~i, j~ thỏa mãn.

Input

• Dòng đầu chứa hai số nguyên dương ~N, M \ (1 \leq N \leq 10^5, \ 1 \leq M \leq 5)~.

• Dòng thứ hai gồm ~N~ số nguyên dươn ~w_1, w_2, ..., w_n~ ~(w_i \leq 10^9)~.

• ~N~ dòng sau, mỗi dòng chứa ~M~ số nguyên dương ~a_{i, 1}, a_{i, 2}, \dots, a_{i, m} \leq 10^9~.

Output

• In ra một số nguyên duy nhất là tổng ~w_i + w_j~ nhỏ nhất, hoặc ~-1~ nếu không tồn tại cặp thỏa mãn.

Scoring

Sample Input 1

4 4
2 7 6 1
10 7 11 5
19 9 8 7
15 18 16 1
7 15 20 9

Sample Output 1

13

Khu vực bạn đang sống có ~n~ thành phố và chúng được nối với nhau bởi ~m~ con đường. Con đường thứ ~i~ nối giữa ~2~ thành phố ~u_i~ và ~v_i~ và bạn cần thời gian ~t_i~ để đi hết con đường thứ ~i~.

Là một đặc vụ ngầm mới gia nhập tổ chức, bạn cải trang thành một shipper. Trong ~q~ ngày tiếp theo, ngoài các đơn hàng bình thường ra, mỗi ngày bạn cần phải vận chuyển một đơn hàng bí mật cho tổ chức. Ngày thứ ~i~ bạn cần vận chuyển đơn hàng bí mật này từ thành phố ~x_i~ đến thành phố ~y_i~.

Để thể hiện được là một đặc vụ chuyên nghiệp, bạn cần phải giao đơn hàng bí mật này trong thời gian ngắn nhất có thể. Trong ~q~ ngày tới, hãy tính xem ngày thứ ~i~ bạn cần mất bao nhiêu thời gian để hoàn thành nhiệm vụ.

Input

• Dòng đầu tiên gồm 3 số nguyên dương ~n~, ~m~ và ~q~.

• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm 3 số nguyên dương ~u_i~, ~v_i~ và ~t_i~.

• ~q~ dòng tiếp theo, dòng thứ ~i~ gồm 2 số nguyên dương ~x_i~ và ~y_i~.

Ràng buộc dữ liệu

• ~1 \leq n, q \leq 10^5~.

• ~n-1 \leq m \leq n+30~.

• ~1 \leq u_i, v_i, x_i, y_i \leq n~.

• ~1 \leq t_i \leq 2 \cdot 10^5~.

• Dữ liệu đảm bảo liên thông giữa ~n~ thành phố.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ chứa một số nguyên là thời gian giao hàng ngắn nhất trong ngày ~i~.

Scoring

Subtasks

Sample Input 1

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

Sample Output 1

13
10
11

Sample Input 2

5 5 3
1 2 5
2 3 5
3 4 4
4 5 1
5 1 2
1 3
2 5
2 4

Sample Output 2

7
7
8

Hưng vừa được nhận vào Cao Chuyên Chú Thuật, và nhiệm vụ đầu tiên của thầy Gojo đưa ra đó là ... phân loại chú vật.

Có ~n~ chủ vật được đánh số từ ~1~ tới ~n~, tuy nhiên Hưng không biết được chúng mang năng lượng dương hay năng lượng âm. Trong thế giới chủ thuật, khi đặt hai chú vật cạnh nhau và niệm chú, chúng sẽ đẩy nhau ra (phản chuyển thuật thức??!) nếu mang năng lượng cùng dấu ((âm, âm), hoặc (dương, dương)), và ngược lại, chúng sẽ hút nhau lại nếu mang năng lượng khác dấu ((âm, dương), hoặc (dương, âm)).

Do Hưng mới vào nghề nên khả năng cảm nhận chú thuật còn yếu, thầy quyết định sẽ thử thách trí thông minh của Hưng thay vì thuật thức bằng cách làm ~q~ truy vấn, mỗi truy vấn thuộc một trong ~3~ loại sau:

• ~0~ ~x~ ~y~ (~1 \le x, y \le n~): cho biết hai chú vật ~x~ và ~y~ đẩy nhau khi niệm chú.

• ~1~ ~x~ ~y~ (~1 \le x, y \le n~): cho biết hai chú vật ~x~ và ~y~ hút nhau khi niệm chú.

• ~2~ ~x~ ~y~ (~1 \le x, y \le n~): đoán xem hai chú vật ~x~ và ~y~ sẽ hút nhau hay đẩy nhau khi niệm chú.

Dù trình độ có hạn nhưng Hưng muốn thể hiện với thầy, vì vậy Hưng muốn nhờ bạn đoán chính xác đáp án ở mỗi truy vấn loại ~2~.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~n~ và ~q~ (~1 \le n, q \le 2 * 10^5~).

• ~q~ dòng tiếp theo, mỗi dòng có dạng thuộc một trong ~3~ loại ở trên.

Output

• Với mỗi truy vấn loại ~2~, bạn hãy giúp Hưng in ra ~0~ nếu hai chú vật đẩy nhau, ~1~ nếu chúng hút nhau, và ~-1~ nếu chưa thể chắc chắn.

Scoring

Sample Input 1

5 5
1 1 3
1 1 5
0 1 2
2 2 3
2 2 4

Sample Output 1

1
-1

Sample Input 2

6 7
0 2 5
1 1 2
0 1 3
2 3 2
1 4 3
2 2 6
2 4 5

Sample Output 2

1
-1
0

Notes

Giải thích bộ test thứ hai:

• Có thể xác định các chú vật ~1~, ~3~ mang năng lượng dương, các chú vật ~2~, ~4~, ~5~ mang năng lượng âm (hoặc ngược lại) và chú vật ~6~ chưa xác định năng lượng.

• Từ đó ta biết được chú vật ~2~ và ~3~ hút nhau, ~4~ và ~5~ đẩy nhau còn ~2~ và ~6~ chưa chắc chắn.

Một dãy ~b~ được định nghĩa là độc lập chính phương nếu như không tồn tại bất kì dãy con khác rỗng nào của ~b~ có tích là một số chính phương.

Cho dãy ~a~ gồm ~n~ phần tử nguyên dương, hãy tìm dãy con dài nhất của ~a~ sao cho nó độc lập chính phương.

Input

• Dòng đầu tiên gồm một số nguyên ~n~ (~1 \le n \le 1000~)— độ dài của dãy ~a~.

• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, a_3, \dots ,a_n~ (~1 \le a_i \le 10^4~).

Output

• In ra độ dài của dãy con dài nhất của ~a~ sao cho dãy này độc lập chính phương.

Scoring

Sample Input 1

4
5 6 4 30

Sample Output 1

2