Dãy Con Tốt Nhất

Farmer John có một xâu nhị phân độ dài $N$, ban đầu toàn số 0. Anh thực hiện $M$ thao tác lật (flip), mỗi thao tác đảo tất cả ký tự từ vị trí $l$ đến $r$ ($0\to 1$, $1\to 0$).

Sau đó trả lời $Q$ truy vấn. Mỗi truy vấn cho ba số $l,r,k$: tìm dãy con (subsequence) có thứ tự từ điển lớn nhất độ dài $k$ từ đoạn $[l,r]$ của xâu. Kết quả được biểu diễn dưới dạng giá trị nhị phân modulo ${10}^9+7$.

Cụ thể, nếu dãy con tìm được là $s_1{s}_2\dots s_k$, in ra ${\sum }_{i=0}^{k-1}{2}^i·s_{k-i}\left(\mathrm{mod}{10}^9+7\right)$.

Dữ liệu vào

• Dòng 1: Ba số nguyên $N,M,Q$ ($1\le N\le {10}^9$, $1\le M\le 2\times {10}^5$, $1\le Q\le 2\times {10}^5$)
• $M$ dòng tiếp theo: Hai số $l,r$ là đoạn cần lật ($1\le l\le r\le N$)
• $Q$ dòng tiếp theo: Ba số $l,r,k$ ($1\le l\le r\le N$, $1\le k\le r-l+1$)

Dữ liệu ra

• $Q$ dòng, mỗi dòng là kết quả của truy vấn tương ứng modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le {10}^9$
• $1\le M,Q\le 2\times {10}^5$

Ví dụ