Cho cơ số \(p\in\{2,3\}\). Ta định nghĩa các phép toán theo từng chữ số trong cơ số \(p\) như sau.

Với \(0\le x<p^d\), viết biểu diễn cơ số \(p\) đủ \(d\) chữ số của \(x\) là

Định nghĩa \(\operatorname{popcount}_p(x)\) là số chữ số khác \(0\):

Với \(0\le x,y<p^d\), gọi các chữ số của \(x,y\) lần lượt là \(x_i,y_i\). Ba phép toán sau tạo số \(z=(z_{d-1}\ldots z_1z_0)_p\):

1. AND cơ số \(p\): \(x\operatorname{and}_p y\), với \(z_i=\min(x_i,y_i)\).
2. OR cơ số \(p\): \(x\operatorname{or}_p y\), với \(z_i=\max(x_i,y_i)\).
3. XOR cơ số \(p\) (cộng từng chữ số không nhớ): \(x\operatorname{xor}_p y\), với \(z_i=(x_i+y_i)\bmod p\).

Cho hai dãy \(a,w\) có độ dài \(n\) và dãy \(z\) có độ dài \(p^d\), trong đó \(0\le a_i<p^d\).

Với mỗi \(0\le u<p^d\) và ba hệ số không âm \(A,B,C\), định nghĩa dãy sinh \(F(u)\) như sau. Với \(1\le i\le n\), đặt

\(F(u)\) là dãy nhận được khi sắp xếp \(b_1,b_2,\ldots,b_n\) theo thứ tự không giảm.

Có \(q\) truy vấn. Mỗi truy vấn cho \(A,B,C,l_1,r_1,l_2,r_2\) và yêu cầu tính

Lưu ý rằng dãy \(F(i)\) trong mỗi truy vấn được xác định bởi chính bộ hệ số \(A,B,C\) của truy vấn đó.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên không âm \(n,d,p\).
• Dòng thứ hai chứa \(n\) số \(a_1,a_2,\ldots,a_n\).
• Dòng thứ ba chứa \(n\) số \(w_1,w_2,\ldots,w_n\).
• Dòng thứ tư chứa \(p^d\) số \(z_0,z_1,\ldots,z_{p^d-1}\).
• Dòng thứ năm chứa số nguyên dương \(q\).
• Mỗi dòng trong \(q\) dòng tiếp theo chứa bảy số \(A,B,C,l_1,r_1,l_2,r_2\).

Dữ liệu ra

Với mỗi truy vấn, in một số nguyên không âm trên một dòng: kết quả theo modulo \(2^{32}\).

Ràng buộc

Chấm điểm

• Tính chất A: bộ ba \((A,B,C)\) giống nhau trong mọi truy vấn.
• Tính chất B: \(l_1=r_1\) trong mọi truy vấn.
• Tính chất C: \(l_1=0\) và \(r_1=p^d-1\) trong mọi truy vấn.

Ví dụ

3 2 2
0 0 2
1 1 2
3 4 4 4
5
1 7 2 0 1 1 1
3 3 5 0 2 2 3
5 2 10 0 1 2 3
3 9 7 0 3 3 3
5 6 1 0 1 2 3

36
304
312
736
182

Khối lượng vào/ra có thể lớn; nên sử dụng phương thức vào/ra nhanh.

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.