Farmer John có một xâu nhị phân độ dài \(N\) (\(1\leq N\leq 10^9\)), ban đầu gồm toàn ký tự \(0\).

Trước tiên, ông sẽ lần lượt thực hiện \(M\) (\(1\leq M\leq 2\cdot 10^5\)) cập nhật trên xâu. Mỗi cập nhật đảo mọi ký tự từ vị trí \(l\) đến \(r\). Cụ thể, đảo một ký tự sẽ đổi nó từ \(0\) thành \(1\) hoặc ngược lại.

Sau đó, ông đưa ra \(Q\) (\(1\leq Q\leq 2\cdot 10^5\)) truy vấn. Với mỗi truy vấn, ông yêu cầu bạn in ra dãy con lớn nhất theo thứ tự từ điển có độ dài \(k\), gồm các ký tự lấy từ xâu con từ vị trí \(l\) đến \(r\). Nếu đáp án là xâu nhị phân \(s_1s_2\dots s_k\), hãy in ra \(\sum_{i=0}^{k-1}2^i\cdot s_{k-i}\) (tức giá trị của xâu khi được hiểu là một số nhị phân) modulo \(10^9+7\).

Dãy con là một xâu có thể thu được từ một xâu khác bằng cách xóa đi một số hoặc không xóa ký tự nào mà không làm thay đổi thứ tự của các ký tự còn lại.

Nhắc lại rằng xâu \(A\) lớn hơn xâu \(B\) có cùng độ dài theo thứ tự từ điển khi và chỉ khi tại vị trí đầu tiên \(i\) (nếu tồn tại) mà \(A_i\neq B_i\), ta có \(A_i>B_i\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(M\) và \(Q\).

\(M\) dòng tiếp theo chứa hai số nguyên \(l\) và \(r\) (\(1\leq l\leq r\leq N\)) — hai đầu mút của mỗi cập nhật.

\(Q\) dòng tiếp theo chứa ba số nguyên \(l\), \(r\) và \(k\) (\(1\leq l\leq r\leq N\), \(1\leq k\leq r-l+1\)) — hai đầu mút của mỗi truy vấn và độ dài dãy con.

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(i\) chứa đáp án cho truy vấn thứ \(i\).

Ví dụ

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

21
13
7
3
1
5
5
3
1

9 1 1
7 9
1 8 8

3

30 1 1
1 30
1 30 30

73741816

Phân nhóm

• Dữ liệu 4: \(N\leq 10\), \(Q\leq 1000\).
• Dữ liệu 5: \(M\leq 10\).
• Dữ liệu 6–7: \(N,Q\leq 1000\).
• Dữ liệu 8–12: \(N\leq 2\cdot 10^5\).
• Dữ liệu 13–20: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 February Contest, Gold — The Best Subsequence. Tác giả: Chongtian Ma.

https://usaco.org/index.php?page=viewproblem2&cpid=1498