Cho hai số nguyên dương ~n~ và ~m~. Bạn được phép thực hiện thao tác sau (không hoặc nhiều lần):

• Chọn một số ~x~ ~(1 \le x \le m)~ bất kỳ, sau đó gán ~n \leftarrow n \times \gcd(n,x)~. Trong đó ~\gcd(n, x)~ là ước chung lớn nhất của ~n~ và ~x~.

Người dân trên hành tinh Arrakis luôn truyền tai nhau về lời tiên tri, nếu ai tìm được cách biến đổi số ~n~ thành ~m~ bằng cách thực hiện ít thao tác nhất, người đó sẽ trở thành vị cứu tinh của vương quốc, The Messiah. Người thực hiện thử thách này phải đưa ra được một dãy thao tác biến đổi số ~n~ bất kỳ thỏa mãn, hoặc phải chỉ ra rằng không tồn tại cách để biến đổi ~n~ thành ~m~ với thao tác đã cho.

Arrakis đang lâm nguy, thánh chiến sắp nổ ra, hãy thử giải quyết thử thách xem liệu bạn có phải là người được chọn!

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 100~).

Mỗi test case gồm một dòng duy nhất chứa hai số nguyên dương ~n, m~ (~1 \leq n, m \leq 10^9~).

Output

Với mỗi test case, nếu như không tồn tại cách biến đổi số ~n~ thành ~m~ sử dụng thao tác đã cho, in ra ~-1~. Ngược lại, in ra trên một dòng số nguyên ~k~ (~1 \le k \le 200~) — số bước ít nhất để biến đổi ~n~ thành ~m~, theo sau đó là ~k~ số nguyên ~x_1, x_2, \ldots, x_k~ — các số nguyên được chọn cho từng bước theo thứ tự.

Nếu có nhiều dãy thao tác có số bước ít nhất để biến đổi ~n~ thành ~m~, hãy in ra dãy thao tác bất kỳ.

Có thể chỉ ra rằng nếu có thể biến đổi từ ~n~ thành ~m~, sẽ tồn tại dãy biến đổi có không quá ~200~ thao tác.

Scoring

Tổng điểm cho bài này là ~1250~.

Sample Input 1

5
2 2
1 6
6 216
2 12
4 2

Sample Output 1

0
-1
2 6 6
-1
-1

Notes

Ở test case đầu tiên, ~n = m = 2~, do đó không thực hiện thêm thao tác nào.

Ở test case thứ hai, ~n = 1~. Ta chỉ có thể chọn được ~x = 1~, và sau đó gán ~n \gets \gcd(1, 1) = 1~. Thao tác không thể thay đổi ~n~, do đó không tồn tại dãy thao tác hợp lệ.

Ở test case thứ 3, ~n = 6~, ~m = 216~. Trùng hợp thay, ~216 = 6^3~, ta có thể lựa chọn 2 thao tác có ~x~ đều bằng ~6~. Có thể chỉ ra rằng không có dãy thao tác để biến ~n = 6~ thành ~m = 216~ với chỉ 1 thao tác.

Ở test case thứ 5, ~n = 4~, ~m = 2~. Do ~n > m~, và các thao tác không thể giảm số ~n~, nên không tồn tại dãy thao tác thỏa mãn.

Upin và Ipin là hai anh em sinh đôi. Hai cậu rất thân thiết và thường chơi cùng nhau trong những lúc không phải học bài. Hôm nay, họ cùng nhau chơi một trò chơi để thi xem ai có khả năng ghi nhớ tốt hơn. Hai bạn tạo ra một xâu kí tự ~s~ chỉ bao gồm các kí tự U và I. Hai bạn cần chọn ra một xâu con~^*~ ~t~ của ~s~, sao cho ~t~ có chứa ít nhất một kí tự U và ít nhất một kí tự I, và tiến hành chơi trò chơi trên xâu ~t~.

Theo sở trường của mình, Upin có thế mạnh ghi nhớ các kí tự U và Ipin có thể mạnh ghi nhớ các kí tự I. Nếu như gọi ~cnt_\texttt{U}~ và ~cnt_\texttt{I}~ lần lượt là số lượng kí tự U và I trong xâu con ~t~, vậy thì kết của của lượt chơi sẽ được quyết định như sau:

• nếu ~cnt_\texttt{U} \geq 2 \cdot cnt_\texttt{I}~, Upin sẽ dành chiến thắng,

• nếu ~cnt_\texttt{I} \geq 2 \cdot cnt_\texttt{U}~, Ipin sẽ dành chiến thắng,

• nếu như không ai chiến thắng, kết quả của lượt chơi là hòa.

Upin và Ipin giao nhiệm vụ trọng tài cho người bạn tốt của mình là Tpin. Tpin cần phải chọn ra xâu con ~t~. Để cuộc chơi có tính quyết định, Tpin cần phải đảm bảo rằng kết của của cuộc chơi không hòa.

Hãy giúp Tpin tìm ra xâu con ~t~ của xâu ~s~ cho trước thỏa mãn, hoặc chỉ ra rằng mọi cách chọn xâu ~t~ đểu cho ra kết quả hòa. Nếu có nhiều cách chọn xâu ~t~, hãy tìm ra cách chọn bất kì.

————————————————————————

~^*~ Xâu ~t~ được gọi là xâu con của ~s~ nếu như ~t~ có thể được tạo thành bằng cách xóa đi (không hoặc nhiều) ký tự ở đầu ~s~, và xóa đi (không hoặc nhiều) ký tự ở cuối ~s~.

Input

Dòng đầu tiên chứa một số nguyên ~q~ (~1 \leq q \leq 10\,000~) — số lượt chơi. Mô tả dữ liệu của mỗi lượt chơi như sau.

Dòng đầu tiên và duy nhất của mỗi lượt chơi chứa một xâu ~s~ (~|s| \le 10^5~) chỉ gồm các kí tự I và U – mô tả xâu được Upin và Ipin lựa chọn cho lượt chơi thứ ~i~.

Dữ liệu đảm bảo tổng độ dài của các xâu ~s~ trong tất cả các lượt chơi không vượt quá ~10^5~.

Output

Đối với mỗi vòng chơi, in ra NO nếu tất cả các chuỗi con ~t~ dẫn đến hòa.

Nếu không, in ra YES và hai số nguyên ~l, r~ ~(1 \leq l \leq r \leq |S|)~ mô tả cách chọn ~t = s_l s_{l + 1} s_{l + 2} \ldots s_r~.

Nếu có nhiều cách chọn, in ra bất kì cách chọn hợp lệ nào.

Bạn có thể xuất câu trả lời ở bất kỳ kiểu chữ nào (chữ hoa hoặc chữ thường). Ví dụ, các chuỗi "yEs", "yes", "Yes", và "YES" sẽ được công nhận là đúng.

Scoring

Tổng điểm cho bài này là ~500~.

Sample Input 1

4
UUUIIIUIIUI
UU
IUUIIUUI
IU

Sample Output 1

Yes 3 11
No
Yes 2 7
No

Notes

Trong lượt chơi đầu tiên, Tpin chọn xâu con ~t~ = "UIIIUIIUI" có ~cnt_\texttt{I} = 6~ và ~cnt_\texttt{U} = 3~. Ipin sẽ dành chiến thắng do điều kiện ~cnt_\texttt{I} \geq 2 \cdot cnt_\texttt{U}~ thỏa mãn.

Trong lượt chơi thứ hai, Tpin không thể tìm được xâu con ~t~ thỏa mãn.

Trong lượt chơi thứ ba, Tpin chọn xâu con ~t~ = "UUIIUU" có ~cnt_\texttt{I} = 2~ và ~cnt_\texttt{U} = 4~. Upin sẽ dành chiến thắng do điều kiện ~cnt_\texttt{U} \geq 2 \cdot cnt_\texttt{I}~ thỏa mãn.

Trong lượt chơi thứ tư, Tpin không thể tìm được xâu con ~t~ thỏa mãn.

Sau khi tốt ngành thời gian học, Kuroni bắt đầu khởi nghiệp và thành lập công ty quản lý thời gian OURO. Sau 1000 năm hoạt động, từ một công ty nhỏ lẻ, OURO đã trở thành công ty quy mô đa vũ trụ. Vừa qua, công ty đã phát hành thêm một loại cổ phiếu mới với lợi nhuận được dự báo sẽ bay lên thẳng mặt trăng.

Có ~n~ cổ đông muốn đầu tư vào loại cổ phiếu này. Các cổ đông được đánh số từ ~1~ đến ~n~. Ban đầu, các cổ đông đều không có cổ phiếu, và tài khoản của họ đều có số tiền bằng ~0~. Có ~q~ sự kiện sẽ diễn ra, các sự kiện thuộc một trong các loại sau:

• ~\texttt{1} \; p \; x~ — Cổ đông ~p~ mua vào ~x~ cổ phiểu (nếu ~x \ge 0~), hoặc bán đi ~|x|~ cổ phiếu (nếu ~x < 0~);

• ~\texttt{2} \; v~ — Công ty kinh doanh có lãi, thu về cổ tức ~v~. Mọi cổ đông đang sở hữu cổ phiếu đều thu về số tiền tỉ lệ với số cổ phiếu. Cụ thể, gọi ~s~ là số cổ phiếu mà một cổ đông sở hữu thì số tiền mà tài khoản của cổ đông đó nhận được sẽ tăng thêm ~s \cdot v~.

• ~\texttt{3} \; p~ — Cổ đông ~p~ sẽ tiến hành rút toàn bộ số tiền hiện có trong tài khoản. Sau khi rút thì số tiền trong tài khoản của cổ đông ~p~ sẽ trở về ~0~.

Với mỗi sự kiện loại ~3~, hãy cho biết số tiền mà cổ đông sẽ thu về được. Vì đáp án có thể rất lớn, bạn có thể in đáp án sau khi chia lấy phần dư cho ~10^9 + 7~.

Input

Dòng đầu tiên gồm hai số nguyên ~n~ và ~q~ (~1 \le n, q \le 5 \cdot 10^5~) — số cổ đông và số sự kiện.

Dòng thứ ~i~ trong ~q~ dòng tiếp theo mô tả sự kiện thứ ~i~ với định dạng như mô tả trong đề bài.

• ~\texttt{1} \; p \; x~ (~1 \le p \le n~, ~-10^9 \le x \le 10^9~) — mô tả sự kiện loại 1. Đảm bảo rằng sau mỗi sự kiện này, không có cổ đông nào có số cổ phiếu âm.

• ~\texttt{2} \; v~ (~1 \le v \le 10^9~) — mô tả sự kiện loại 2.

• ~\texttt{3} \; p~ (~1 \le p \le n~) — mô tả sự kiện loại 3.

Output

Với mỗi sự kiện loại ~3~, in ra số tiền mà cổ đông thu về được sau khi chia lấy phần dư cho ~10^9 + 7~.

Scoring

Tổng điểm cho bài này là ~1500~.

Sample Input 1

3 8
1 1 5
2 3
1 2 10
2 2
3 1
2 4
3 2
3 1

Sample Output 1

25
60
20

Sample Input 2

1 8
1 1 1000
2 1
1 1 -100
2 2
3 1
1 1 -200
2 3
3 1

Sample Output 2

2800
2100

Notes

Trong ví dụ đầu tiên có ~n = 3~ cổ đông. Chỉ có cổ đông ~1~ và ~2~ thực hiện đầu tư.

Bảng dưới đây mô tả các sự kiện có liên quan đến cổ đông ~1~.

Bảng dưới đây mô tả các sự kiện có liên quan đến cổ đông ~2~.

Trong ví dụ thứ hai, có ~n = 1~ cổ đông. Bảng dưới đây mô tả các sự kiện của ví dụ thứ hai.