Nguồn đề - Free Contest 116: https://drive.google.com/file/d/1eJ_po7VF86dLkTnCoLDIvx9d5ScIqYvc/view?usp=sharing

Lời giải: https://drive.google.com/file/d/1fyBawyORfNm4yP0Yqexarbtgw_4V6D/view?usp=sharing

Đất nước X có ~2^N~ hiệp sĩ, hiệp sĩ thứ i có số thứ tự là i (số thứ tự này sẽ được giữ nguyên trong suốt giải đấu). Hằng năm nhà vua sẽ tổ chức một cuộc thi để chọn ra hiệp sĩ mạnh nhất của đất nước. Luật chơi như sau, với mỗi vòng đấu.

• Các hiệp sĩ lần lượt sẽ xếp thành một hàng theo thứ tự tăng dần của số thứ tự.

• Các hiệp sĩ sẽ thi đấu theo thể thức đấu loại trực tiếp, cứ hai hiệp sĩ đứng cạnh nhau sẽ đấu với nhau. Ví dụ: ta có 8 hiệp sĩ thì hiệp sĩ 1 sẽ đấu với hiệp sĩ 2, hiệp sĩ 3 sẽ đấu với hiệp sĩ 4, hiệp sĩ 5 sẽ đấu với hiệp sĩ 6, hiệp sĩ 7 sẽ đấu với hiệp sĩ 8.

• Với mỗi cặp đấu, hiệp sĩ thua sẽ ngay lập tứ bị loại khỏi giải đấu, hiệp sĩ thắng sẽ đi tiếp vào vòng tiếp theo. Cứ lặp đi lặp lại cho đến khi chọn ra được một người thắng cuộc duy nhất.

Được biết rằng mỗi hiệp sĩ sẽ có một chỉ số sức mạnh nhất định, hai hiệp sĩ khác nhau sẽ có chỉ số sức mạnh khác nhau. Trong một trận đấu bất kì, hiệp sĩ có chỉ số sức mạnh cao hơn sẽ luôn thắng hiệp sĩ có chỉ số sức mạnh thấp hơn.

Nhà vua không biết chính xác chỉ số sức mạnh của các hiệp sĩ, nhà vua chỉ biết được là hiệp sĩ có số thứ tự a và hiệp sĩ có số thứ tự b là hai hiệp sĩ có chỉ số sức mạnh cao nhất.

Để giải đấu thêm phần hấp dẫn, nhà vua muốn hai hiệp sĩ có chỉ số sức mạnh cao nhất sẽ gặp nhau ở trận chung kết, là một cận thần đáng tin cậy của nhà vua, nhiệm vụ của bạn là trả lời Q tình huống khác nhau, mỗi tình huống nhà vua sẽ cho bạn biết số thứ tự a và b của hai hiệp sĩ có chỉ số sức mạnh cao nhất, bạn sẽ kiểm tra xem liệu hai hiệp sĩ này có thể gặp nhau ở vòng chung kết hay không.

Input

• Dòng đầu tiên gồm hai số nguyên dương Q và N ~(1 \leq Q \leq 10^5, 1 \leq N \leq 50 )~, lần lượt là số lượng câu hỏi và N của ~2^N~ hiệp sĩ tham gia.
• Q dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương a và b ~(1 \leq a,b \leq 2^N, a \ne b)~ lần lượt là vị trí dự định của hai hiệp sĩ có chỉ số sức mạnh cao nhất.

Output

• Gồm Q dòng, mỗi dòng in ra "yes" nếu hai hiệp sĩ có thể gặp nhau ở vòng chung kết với cặp vị trí này, in ra "no" nếu ngược lại.

Sample Input 1

2 3
1 2
1 8

Sample Output 1

no
yes

Giải thích

Gọi (x,y) là cặp đấu giữa hiệp sĩ có số thứ tự x và hiệp sĩ có số thứ tự y các lượt đấu lần lượt là:

• Vòng 1: (1, 2), (3, 4), (5, 6), (7, 8), vì hiệp sĩ thứ 1 và 2 đã gặp nhau ngay ở vòng đầu tiên nên đáp án cho câu hỏi thứ nhất là "no".
• Vòng 2: (1, 3), (5, 8).
• Vòng 3: (1, 8) đây chính là vòng chung kết nên đáo án câu hỏi thứ hai là "yes".

Chấm điểm

• Subtask 1 (50% số test): Q = 1, ~N \leq 10~.
• Subtask 2 (50% số test): Không có ràng buộc gì thêm.