Nhảy lò cò là một trò chơi dân gian Việt Nam. Thuở bé Lan rất thích chơi trò này. Vì vậy, khi được học môn "Phân tích và thiết kế thuật toán", Lan đã đặt ra một bài toán khá thú vị liên quan tới trò chơi này. Trên mặt phẳng vẽ ~n~ vòng tròn. Các vòng tròn này lại được xếp trên một vòng tròn lớn và được đánh số từ từ ~1~ đến ~n~ theo chiều đi vòng quanh vòng tròn lớn thuận chiều kim đồng hồ. Hai vòng tròn nhỏ liên tiếp nhau theo một chiều đi vòng quanh vòng tròn lớn được gọi là ở bên cạnh nhau.

Người chơi bắt đầu từ vòng tròn đánh số ~1~, mỗi bước nhảy người chơi sẽ di chuyển sang một trong hai vòng tròn bên cạnh. Hãy giúp Lan giải quyết bài toán sau: Đếm xem có bao nhiêu cách khác nhau thực hiện ~k~ bước nhảy bắt đầu từ vòng tròn ~1~ rồi lại quay về vòng tròn ~1~.

Input

Một dòng chứa hai số nguyên dương ~n~ và ~k~ (~3\le n\le 4000, 1\le k \le 10^6~) — số lượng vòng tròn và số lượng bước nhảy.

Output

Một số nguyên là phần dư trong phép chia số lượng cách nhảy tìm được cho ~10^9+7~.

Scoring

Sample Input 1

3 2

Sample Output 1

2

Một hệ thống đèn trang trí gồm ~n~ đèn được đánh số từ ~1~ đến ~n~ và ~n - 1~ đoạn dây nối điều khiển, mỗi đoạn nối một cặp hai đèn khác nhau. Hệ thống dây nối điểu khiển thỏa mãn tính chất sau đây: Không có đoạn dây nào nối một đèn với chính nó; không có hai đoạn dây nào nối cùng một cặp đèn và hơn nữa không tìm được dãy các đèn ~v_1, v_2, ..., v_k, v_1~, trong đó hai đèn liên tiếp là có đoạn dây nối và không có đoạn dây nối nào xuất hiện quá một lần.

Tại mỗi thời điểm, mỗi đèn sẽ sáng màu xanh hoặc đỏ. Bộ điều khiển hệ thống đèn có thể thực hiện tác động nhiều lần việc thay đổi trạng thái các đèn, mỗi lần tác động là thay đổi màu của một đèn nào đó và tất cả các đèn có dây nối với nó, cụ thể nếu đèn đang sáng màu xanh sẽ chuyển sang sáng màu đỏ, ngược lại nếu đèn đang sáng màu đỏ sẽ chuyển sang sáng màu xanh.

Cho biết trạng thái ban đầu về màu của ~n~ đèn và thông tin về các dây nối điều khiển, hãy tìm cách điều khiển để tất cả các đèn sáng màu xanh.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n, T~ (~n\le 3000~, ~T\le 500~) — số lượng đèn và số trường hợp thử nghiệm.

Mỗi dòng trong số ~n - 1~ dòng tiếp theo gồm hai số nguyên ~u, v~ (~1\le u, v\le n~, ~u\ne v~) — có đoạn dây nối giữa hai đèn ~u~ và ~v~.

Dòng thứ ~i~ trong số ~T~ dòng cuối cùng gồm ~n~ số nguyên ~c_{i,1}, c_{i,2}, ..., c_{i,m}~, trong đó ~c_{ij} = 1~ nếu đèn ~j~ sáng màu xanh và ~c_{ij} = 0~ nếu đèn ~j~ sáng màu đỏ trong thử nghiệm thứ ~i~.

Dữ liệu đảm bảo hệ thống dây nối điều khiển thoả mãn đề bài.

Output

Với mỗi thử nghiệm, in ra ~-1~ nếu không tồn tại cách điều khiển, ngược lại in ra trên một dòng:

• Số nguyên ~s~ (~s \leq n~) — số lần dùng bộ điều khiển.

• Tiếp theo là ~s~ số nguyên ~l_1, l_2, ..., l_s~ mô tả cách điều khiển, trong đó tác động thứ ~h~ (~1\le h\le s~) làm đảo màu của đèn ~l_k~ và các đèn nối với ~l_k~.

Scoring

Sample Input 1

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

Sample Output 1

2 2 3

Trong lúc ôn tập phần hình học để thi học sinh giỏi tin học, Hải quan sát mối quan hệ giữa các cung tròn được tạo bởi giao của một số các đường thẳng với một đường tròn như sau:

Cho một đường tròn xác định bởi tọa độ tâm ~(x, y)~, bán kính ~r~ và ~n~ đường cát tuyến, trong đó đường cát tuyến thứ ~i~ được xác định bởi phương trình ~a_i x + b_i y = c_i~. Biết rằng không có đường cát tuyến nào đi qua tâm đường tròn. Một đường cát tuyến nếu cắt đường tròn tại hai điểm ~A~ và ~B~ thì cung ~\widehat{AB}~ nhỏ của đường tròn được gọi là cung đặc trưng của đường cát tuyến đó. Lưu ý: nếu đường cát tuyến tiếp xúc với đường tròn thì cung đặc trưng suy biến thành một điểm.

Tiếp theo, Hải dựng đồ thị đơn vô hướng ~G = (V, E)~, trong đó mỗi đỉnh trong đồ thị tương ứng với một cung đặc trưng của đường tròn, và hai đỉnh trong ~V~ có cạnh nối trong ~E~ khi và chỉ khi hai cung đặc trưng tương ứng của hai đỉnh này có điểm chung.

Gọi hai cạnh khác nhau ~(u_1, v_1)~ và ~(u_2, v_2)~ trong ~E~ là độc lập nếu như không tồn tại đỉnh ~t \in V~ sao cho cả hai điều kiện sau đều đúng:

• Cạnh ~(u_1, t)~ hoặc cạnh ~(v_1, t)~ nằm trong ~E~.

• Cạnh ~(u_2, t)~ hoặc cạnh ~(v_2, t)~ nằm trong ~E~.

Hải muốn tìm ~E'~ là tập con lớn nhất của ~E~ sao cho mọi cặp cạnh trong ~E'~ đều độc lập. Hãy giúp Hải giải bài này nhé!

Input

Dòng thứ nhất chứa số nguyên dương ~T~ (~1 \le T \le 10~) là số lượng bộ dữ liệu. Mô tả của mỗi bộ dữ liệu như sau:

Dòng đầu tiên chứa ba số nguyên ~x~, ~y~, ~r~ (~|x|, |y|, r \le 10^9~) lần lượt là tọa độ tâm và bán kính của đường tròn.

Dòng thứ hai chứa một số nguyên dương ~n~ (~1 \le n \le 50\,000~) là số lượng đường cát tuyến.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa ba số nguyên ~a_i, b_i, c_i~ (~|a_i|, |b_i|, |c_i| \le 10^9~) là các tham số của đường cát tuyến thứ ~i~.

Dữ liệu đảm bảo là trong số các giao điểm của các đường cát tuyến với đường tròn không có hai điểm nào cách nhau ở khoảng cách nhỏ hơn ~10^{-3}~.

Output

In ra ~T~ dòng, mỗi dòng chứa một số nguyên là số lượng cạnh nằm trong tập độc lập lớn nhất. Nếu không tồn tại cạnh nào, in ra ~-1~.

Scoring

Sample Input 1

1
0 0 5
8
0 1 2
11 3 40
7 -3 29
1 -2 10
-1 -2 9
1 0 -2
-6 7 42
0 1 5

Sample Output 1

2

Được biết Hồng đang theo học chuyên đề xử lý dữ liệu lớn, Sơn đề nghị Hồng luyện tập với bài toán sau đây:

Cho một dãy ~h~ gồm ~n~ số nguyên ~h_0,h_1,\ldots,h_{n-1}~. Cần thực hiện ~q~ truy vấn, mỗi truy vấn thuộc một trong hai dạng:

1. Thêm một số nguyên ~x~ vào dãy ~h~.

2. Sắp xếp dãy ~h~ hiện tại theo thứ tự không giảm, sau đó tính tổng ~k~ phần tử có chỉ số ~i_0,i_1,\ldots,i_{k-1}~.

Các chỉ số trong truy vấn loại ~2~ sẽ được xác định bởi bốn thông số ~k, start, a, b~ theo công thức sau: $$i_j = \begin{cases} start \bmod size & \text{nếu } j = 0 \\ (i_{j-1}\cdot a + b) \bmod size & \text{nếu } j > 0 \end{cases}$$

với ~size~ là kích thước của dãy ~h~ hiện tại.

Input

Dòng đầu tiên gồm một số nguyên dương ~T~ (~T\le 5~) — số bộ dữ liệu. Mô tả của mỗi bộ dữ liệu như sau:

Dòng đầu tiên của mỗi bộ dữ liệu gồm hai số nguyên dương ~n, q~ (~n\le 100000~, ~q\le 20000~) — kích thước ban đầu của dãy ~h~ và số truy vấn.

Dòng tiếp theo của mỗi bộ dữ liệu gồm ~n~ số nguyên ~h_0,h_1,\ldots,h_{n-1}~ (~1\le h_i\le 10^9~).

Mỗi dòng trong ~q~ dòng cuối cùng của mỗi bộ dữ liệu bắt đầu bằng một chữ cái ~cmd~.

• Nếu ~cmd=\texttt{A}~, thì tiếp theo là một số nguyên ~x~ (~1\le x\le 10^9~) là số cần được thêm vào dãy ~h~.

• Nếu ~cmd=\texttt{B}~, thì tiếp theo là bốn số nguyên ~k, start, a, b~ (~1\le start, a,b\le 1000~, ~k\le 10000~) mô tả một truy vấn loại ~2~.

Output

Với mỗi bộ dữ liệu, in ra một dòng gồm đáp án của các truy vấn loại ~2~.

Scoring

Sample Input 1

2
2 3
42 13
B 2 2 1 1
A 17
B 5 2 5 6
10 13
42 13 7 11 5 666 13 17 20 6
B 3 6 7 8
B 13 1 11 9
A 23
B 13 1 11 9
A 23
A 8
B 3 3 3 3
B 7 17 9 11
A 12
B 1 8 3 5
A 31
A 28
B 77 17 11 13

Sample Output 1

55 160
64 1477 510 679 99 17 1236

Notes

Trong bộ dữ liệu đầu tiên, dãy ~h~ ban đầu sau khi sắp xếp là ~[13,42]~.

• Truy vấn đầu tiên cần tính tổng tại các chỉ số ~0,1~: ~13+42=55~.

• Truy vấn thứ hai cần thêm ~17~ vào dãy ~h~, sau khi sắp xếp ta được: ~[13,17,42]~.

• Truy vấn thứ ba cần tính tổng tại các chỉ số ~2,1,2,1,2~: ~42+17+42+17+42=160~.