Subtask 1: Tiền xử lí, tạo mảng ~b[i]~ lưu tất cả những ~mask~ có số bit được bật là ~i~. Với mỗi truy vấn loại ~3~, ta chỉ cần duyệt qua mọi ~mask~ trong ~dp[x]~ và xem thử nếu cách chọn cách phần tử trong ~A~ là ~mask~ thì mang lại giá trị nào và cập nhật cho kết quả. Vì ~|A| \leq 12~ nên ~size~ của ~b[i]~ tối đa là ~\binom{12}{6}~.

Độ phức tạp tệ nhất: ~O(M \cdot \binom{12}{6} \cdot 6)~.

Subtask 2: Tham lam như bước đầu của subtask 3.

Subtask 3: Có nhiều sol, sau đây là sol chia căn + DP SOS:

• Đặt ~dp[mask]~ là số lượng phần tử trong dãy ~A~ có ~submask~ là ~mask~. ~dp[mask]~ có thể được tính dễ dàng bằng dp SOS và một mảng ~cnt[x]~ là số lượng phần tử mang giá trị ~x~ hiện có trong mảng ~A~. Base: ~dp[x]~ = ~cnt[x]~.

• Giả sử không có truy vấn loại ~1~ và ~2~, với mỗi truy vấn loại ~3~, ta có thể tham lam bằng cách for ngược bit từ ~k - 1~ về ~0~ và xem thử liệu bật bit thứ ~i~ có được không. Bit thứ ~i~ sẽ bật được nếu số lượng phần tử trong dãy ~A~ có bit thứ ~i~ được bật là ~\geq x~, nếu bật được thì ta cập nhật kết quả ~res = res | 2 ^ i~.

• Nếu có thêm truy vấn loại ~1~ và ~2~, ta cũng sử dụng thuật như trên nhưng duy trì thêm 2 vector ~add~ và ~del~ lần lượt lưu những phần tử được thêm vào mảng ~A~ và xóa khỏi mảng ~A~. Với mỗi truy vấn loại ~3~, ta cũng sẽ duyệt như trên và qua 2 vector mới tạo và dễ dàng tính được giá trị ~dp[res | 2 ^ i] + dem~ là số lượng phần tử trong mảng ~A~ có submask là ~res | 2^i~. Kiểm tra xem nếu giá trị đó có ~\geq x~ không và cập nhật ~res~. Với 2 vector ~add~ và ~del~, mỗi khi tổng của 2 vector này lớn hơn ~\sqrt{M}~ thì ta cập nhật cho mảng ~dp~ và empty 2 vector đó.

  Độ phức tạp: ~O(k \cdot 2 ^ k + \sqrt{M} \cdot k \cdot 2 ^ k )~.

#include <bits/stdc++.h>

 using namespace std;

 const int MAX = 75e3;
 const int K = 18;

 int N, M, k, t, x, v, res, S;
 int a[MAX + 2], dp[(1 << K) + 2], cnt[(1 << K) + 2];
 vector <int> ad, dele;

 void pre(){
     for (int i = 0; i < (1 << k); ++i) dp[i] = cnt[i];
     for (int bit = 0; bit < k; ++bit) 
       for (int mask = (1 << k) - 1; mask >= 0; --mask) if (!(mask & (1 << bit)))
         dp[mask] += dp[mask ^ (1 << bit)];
 }

 void solve(){
     cin >> N >> M >> k;
     S = (int)sqrt(M) * 1.5;
     for (int i = 1; i <= N; ++i){
         cin >> a[i];
         ++cnt[a[i]];
     }
     pre();
     for (int query = 1; query <= M; ++query){
         res = 0;
         cin >> t;
         if (t == 3){
             cin >> x;
             res = 0;
             for (int bit = k - 1; bit >= 0; --bit){
                 int dem = 0;
                 int new_res = (res | (1 << bit));
                 for (auto x: ad)
                     if ((x & new_res) == new_res)
                         ++dem;
                 for (auto x: dele)
                     if ((x & new_res) == new_res)
                         --dem;
                 if (dp[new_res] + dem >= x) res = new_res;
             }
             cout << res << "\n";
         }
         else{
             cin >> v;
             if (t == 1){
                 ad.push_back(v);
                 ++cnt[v];
             }
             else{
                 dele.push_back(v);
                 --cnt[v];
             }
         }
         if ((int)ad.size() + (int)dele.size() >= S){
             ad.clear(), dele.clear();
             pre();
         }
     }
 }

 signed main(){
     ios::sync_with_stdio(0);
     cin.tie(0);

     int test = 1;
     if (0) cin >> test;
     while (test--){
         solve();
     }
 }