Giả sử số hàng không bị giới hạn bởi ~k~. Điều kiện cần và đủ để Saba có thể về nhà an toàn là ~r~ phải có cùng bit bật cao nhất với ~l~.

• Nếu như ~l~ và ~r~ cùng bit bật cao nhất là ~i~, tồn tại một đường đi thẳng từ cột ~l~ đến ~r~ thông qua hàng thứ ~i~. Lý do là khi đó mọi số nằm giữa ~l~ và ~r~ đều sẽ cùng có bit cao nhất với ~l~.

• Nếu như ~l~ và ~r~ không cùng bit bật cao nhất, giả sử ~x~ là số nhỏ nhất sao cho ~l < 2^x~. Ta có:

  • Toàn bộ các số từ ~l~ đến ~2^x - 1~ đều có cùng bit bật cao nhất.

  • ~2^x \le r~. Nếu không ~r~ và ~l~ sẽ có cùng bit bật cao nhất.

  • Do ~2^x - 1~ và ~l~ cùng bit bật cao nhất, nên tồn tại đường đi từ ~l~ đến ~2^x - 1~.

  • Tuy nhiên do ~2^x \wedge (2^x - 1) = 0~, nên ta không thể đi từ ~2^x - 1~ đến ~2^x~ được.

  Từ các dữ kiện trên, ta không thể đi từ ~l~ đến ~r~, do ta không thể đi từ ~l~ đến ~2^x~ (là một điểm nằm giữa ~l~ và ~r~) được.

Với chứng minh trên, ta cũng có cách kiểm tra nhanh ~l~ và ~r~ có cùng bit bật cao nhất hay không, bằng cách tìm ra số ~x~ dựa vào ~l~ và kiểm tra xem ~r~ có nhỏ hơn ~2^x~ không.

Khi số hàng bằng ~k~, quan sát về đường đi cũng tương tự, là ta có thể sử dụng một đường đi thẳng qua bit cao nhất, tuy nhiên lúc này sẽ là qua bit bật cao nhất của ~l \bmod 2^k~. Nếu như ta tìm được số ~x'~ nhỏ nhất sao cho ~(l \bmod 2^k) < 2^{x'}~, vậy đáp án là YES nếu như ~r < l + 2^{x'}~. Chứng minh cũng tương tự như trên.

Số ~x'~ có thể tìm trong ~O(1)~, tuy nhiên các bài giải chạy trong ~O(\log l)~ vẫn được chấp nhận, bao gồm việc xét toàn bộ bit bật thay vì chỉ tìm mỗi bit cao nhất.

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int64_t l, r; int k; cin >> l >> r >> k;
    if (r - l >= (1LL << k)) {
        cout << "NO\n"; return;
    }
    l %= (1LL << k); r %= (1LL << k);
    if (l > r) {
        cout << "NO\n"; return;
    }
    if (l == 0 && r == 0) {
        cout << "NO\n"; return;
    }
    cout << (bit_width((uint64_t)l) == bit_width((uint64_t)r) ? "YES\n" : "NO\n");
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; cin >> t;
    while (t--) {
        solve();
    }
}