Lớp học Bedao đang phải cùng nhau làm một đề thi! Ở mỗi thời điểm, sẽ có hai khả năng xảy ra:

• ~1\ x~ (~0 \le x \le 10^5~): Một học sinh mới gia nhập lớp học. Học sinh này sẽ có khả năng giải được bài thuộc dạng ~x~. Nếu ~x = 0~, học sinh này có thể giải được mọi dạng bài!

• ~2\ x~ (~1 \le x \le 10^5~): Một bài tập thuộc dạng ~x~ được đưa vào đề thi, và lớp cần phải cử ra ngay một bạn để giải. Vì độ khó của bài tập, mỗi học sinh chỉ có thể giải được tối đa ~1~ bài trong khoảng thời gian thi.

Nếu không thể giải được toàn bộ bài tập, lớp Bedao sẽ không thể vượt qua đề kiểm tra. Hãy cho biết, các học sinh có thể giải được toàn bộ bài tập hay không?

Input

Mỗi test bao gồm nhiều test cases.

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

• Dòng đầu tiên của mỗi test case gồm số nguyên dương ~q~ (~1 \le q \le 10^5~) — số sự kiện của bài toán.

• Dòng thứ ~i~ trong ~q~ dòng tiếp theo của test case gồm hai số nguyên ~p~ (~1 \le p \le 2~), ~x~ (~0 \le x \le 10^5~) mô tả một trong hai sự kiện nêu ở đề bài.

Dữ liệu đã cho đảm bảo tổng của ~q~ ở tất cả các test cases sẽ không vượt quá ~5 \cdot 10^5~.

Output

• Với mỗi test case, in ra ~\texttt{YES}~ nếu lớp học Bedao có thể giải được toàn bộ bài tập; ngược lại in ra ~\texttt{NO}~.

Sample Input 1

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

Sample Output 1

YES
NO

Note

Ở test case đầu tiên, các sự kiện xảy ra tuần tự như sau:

• Một học sinh (A) có khả năng giải bài thuộc dạng ~3~ gia nhập lớp học.

• Một học sinh (B) có khả năng giải mọi loại bài gia nhập lớp học.

• Một bài tập thuộc dạng ~6~ được đưa vào đề thi. Bạn B được cử đi giải.

• Một học sinh (C) có khả năng giải bài thuộc dạng ~5~ gia nhập lớp học.

• Một bài tập thuộc dạng ~3~ được đưa vào đề thi. Bạn A được cử đi giải.

Ở test case thứ hai, một bài tập thuộc dạng ~1~ được đưa vào đề thi nhưng không ai có thể giải được.

Cho hai phân số ~\frac{0}{1}~ và ~\frac{1}{0}~. Ta tạo ra dãy vô hạn bằng cách: xét hai phân số ~\frac{a}{b}~ và ~\frac{c}{d}~ đang ở cạnh nhau, ta thêm phân số ~\frac{a\ +\ c}{b\ +\ d}~ vào vị trí giữa. Dãy số có thể tạo ra cây nhị phân vô hạn đầy đủ như hình minh hoạ:

hình minh hoạ

Ta lần lượt sử dụng ~L~ và ~R~ thể hiện việc đi sang cây con trái và cây con phải khi đi từ gốc ~\frac{1}{1}~. trungnotchung có ~q~ thắc mắc bấy lâu nay: tìm đường đi ngắn nhất giữa hai phân số ~\frac{1}{1}~ và ~\frac{x}{y}~.

Input

• Dòng đầu tiên nhập số nguyên dương ~q~ ~(1 \le q \le 100)~ - số câu hỏi của bạn Trung.

• Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa hai số nguyên dương ~(x_i, y_i)~ trong câu hỏi thứ ~i~ mà bạn Trung đưa ra. Dữ liệu đảm bảo luôn có ít nhất một đường đi giữa hai phân số ~\frac{1}{1}~ và ~\frac{x_i}{y_i}~ ~(x_i, y_i \le 9 \times 10^{18},\ max(x_i, y_i) > 1,\ gcd(x_i, y_i) = 1)~.

Output

• In ra ~q~ dòng là đáp án của các câu hỏi.

Subtask

• ~20\%~ số test có độ dài xâu kết quả không vượt quá ~17~.

• ~70\%~ số test có ~x_i, y_i \le 10^9~.

• ~10\%~ số test không có ràng buộc gì thêm.

Sample Input 1

2
5 7
878 323

Sample Output 1

LRRL
RRLRRLRLLLLRLRRR

Notes

Ở testcase đầu tiên, đường đi ngắn nhất là ~\frac{1}{1}~ ~\stackrel{L}{\rightarrow}~ ~\frac{1}{2}~ ~\stackrel{R}{\rightarrow}~ ~\frac{2}{3}~ ~\stackrel{R}{\rightarrow}~ ~\frac{3}{4}~ ~\stackrel{L}{\rightarrow}~ ~\frac{5}{7}~.

Copium và Illya cảm thấy ngán ngẩm vì ăn mãi không hết táo nên đã nghĩ ra một trò chơi. Trò chơi đó như sau:

Có hai hàng táo, mỗi hàng lần lượt có ~n~ và ~m~ quả táo. Khi đến lượt một người chơi, người đó sẽ thực hiện thao tác sau: lấy ~x~ trái táo trong hàng có nhiều táo hơn, sao cho ~x > 0~ và ~x~ là bội của số táo nhỏ hơn.

Nếu đến lượt của người chơi hiện tại mà một trong hai hàng táo trống, thì người còn lại là người chiến thắng.

Hai người sẽ cùng nhau chơi trò chơi ~q~ lần. Ở mỗi lần chơi, Copium là người đi trước. Biết cả hai người chơi đều chơi tối ưu, hãy xác định Copium hay Illya là người chiến thắng trong mỗi lần chơi.

Input

• Dòng đầu tiên chứa số nguyên ~q~ ~(1 \le q \le 1000)~.

• ~q~ dòng sau, mỗi dòng chứa hai số nguyên ~n~ và ~m~ ~(1 \le n, m < 2^{31})~.

Output

• In ra ~q~ dòng, mỗi dòng thể hiện người chiến thắng tương ứng của mỗi lần chơi. Nếu copium thắng, hãy in ra ~\texttt{copium}~, ngược lại, in ra ~\texttt{illya}~.

Subtask

• ~30\%~ số test có ~1 \le n, m \le 1000~.

• ~70\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

3
1 2
3 4
6 9

Sample Output 1

copium
illya
illya

Notes

Ở test case đầu tiên, Copium sẽ lấy hết ~2~ trái táo ở hàng ~2~. Khi đến lượt Illya, vì hàng ~2~ trống nên Copium là người chiến thắng.

Ở test case thứ hai, Copium chỉ có thể lấy đi ~3~ trái táo ở hàng ~2~. Lúc này, số táo ở hai hàng lần lượt là ~3~ và ~1~. Vì thế, Illya sẽ chỉ cần lấy hết ~3~ trái táo ở hàng ~1~ để trở thành người chiến thắng.

Mỗi khi đến tiết thể dục, các học sinh nam lại tụ họp trên sân cỏ để đá bóng. Hiện tại có ~2n~ học sinh trên sân, cần chia ra hai đội, mỗi đội ~n~ người để đá bóng. Các học sinh được đánh số từ ~1~ đến ~2n~.

Có ~m~ cặp học sinh là bạn bè của nhau, họ có xu hướng phối hợp với nhau tốt hơn là hai người không phải bạn bè. Mỗi cặp bạn bè sẽ có một chỉ số gọi là sức mạnh tình bạn.

Ta định nghĩa sức mạnh của một đội là tổng sức mạnh tình bạn nằm trong đội đó. Để trận đấu diễn ra một cách công bằng nhất, chênh lệch sức mạnh giữa hai đội phải nhỏ nhất có thể.

Yêu cầu: Cho biết ~n~ và ~m~ cặp bạn bè, tìm cách chia đội sao cho chênh lệch sức mạnh giữa hai đội là nhỏ nhất.

Input

• Dòng đầu tiên gồm hai số nguyên ~n, m\ (1 \leq n \leq 200,\ 0 \leq m \leq n \times (2n - 1))~.

• ~m~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~u,\ v,\ w\ (1 \leq u < v \leq 2n)~ thể hiện một cặp bạn bè.

Dữ liệu đảm bảo tổng sức mạnh bạn bè không vượt quá ~2n \times 2n~.

Output

• In ra chênh lệch nhỏ nhất có thể đạt được nếu chia đội một cách tối ưu.

Subtask

• ~20\%~ số test có ~n \leq 8~.

• ~60\%~ số test có ~n \leq 50~.

• ~20\%~ số test không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

2

Note

Một cách chia thỏa mãn đề bài là đội thứ nhất gồm các học sinh ~1,\ 3~ và đội thứ hai gồm các học sinh ~2,\ 4~. Chênh lệch sức mạnh giữa hai đội sẽ là ~|1 - 3| = 2~.

Cả thế giới đang phải chịu ảnh hưởng hết sức nặng nề của một chủng virus mới mang tên "khô bồng". Người bị nhiễm chủng virus này có các biểu hiện như: đi chơi Noel một mình, ngại tiếp xúc với đám đông, ... và đặc biệt là thường xuyên cảm thấy cô đơn, trống vắng trong lòng, mặc cảm với những người xung quanh. Ngoài những ảnh hưởng nặng nề cho người bị nhiễm, loại virus này còn nguy hiểm bởi khả năng lây lan trong vòng ~1~ giây.

Để nghiên cứu và tìm ra vaccine chống lại virus, các nhà khoa học đã mời được ~n~ tình nguyện viên tham gia khảo sát để tìm hiểu quá tính lây lan của nó. Cuộc khảo sát diễn ra trong vòng ~t~ giây, ~n~ tình nguyện viên ngồi trên một chiếc bàn hình tròn đánh số lần lượt từ ~1~ đến ~n~ theo chiều kim đồng hồ. Ban đầu, các nhà khoa học sẽ cho ~m~ người bị nhiễm virus. Sau đó cứ mỗi giây, virus sẽ nhân đôi, tuy nhiên chúng sẽ không ở lại chủ thể cũ mà sẽ lây nhiễm sang hai người là người thứ ~k~ tính từ người ngồi bên trái chủ thể theo chiều kim đồng hồ và người thứ ~k~ tính từ người bên phải chủ thể theo chiều ngược kim đồng hồ.

Hãy giúp các nhà khoa học tính số lượng người bị nhiễm virus "khô bồng" sau khi cuộc khảo sát kết thúc để phát người yêu cho họ.

Input

• Dòng đầu tiên chứa bốn số nguyên ~n~, ~m~, ~k~, ~t~ lần lượt là số tình nguyện viên tham gia khảo sát, số người bị nhiễm bệnh ban đầu, khoảng cách lây lan của virus và thời gian cuộc khảo sát diễn ra ~(1 \leq k < n \leq 10^{18}, 0 \leq t \leq 10^{18}, 1 \leq m \leq min(n, 10^6))~.

• Dòng thứ hai chứa ~m~ số nguyên dương phân biệt ~p_1, p_2, ..., p_n~ là chỉ số của những người bị nhiễm virus ban đầu.

Output

• Một số duy nhất là số người bị nhiễm bệnh sau khi cuộc khảo sát kết thúc.

Subtask

• ~30 \%~ số test có ~n, t \leq 3000~.

• ~30 \%~ số test khác có ~m = 1~.

• ~40 \%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

12 2 1 3
1 8

Sample Output 1

8

Note

Ở giây thứ ~0~, hai người được đánh số ~1~ và ~8~ bị nhiêm bệnh.

Ở giây thứ ~1~, bốn người được đánh số ~2~, ~7~, ~9~ và ~12~ bị nhiễm bệnh.

Ở giây thứ ~2~, sáu người được đánh số ~1~, ~3~, ~6~, ~8~, ~10~, ~11~ bị nhiễm bệnh.

Ở giây thứ ~3~, tám người được đánh số ~2~, ~4~, ~5~, ~7~, ~9~, ~10~, ~11~, ~12~ bị nhiễm bệnh.