پرانتز (Parentheses)

آقای الف یک آرایه به طول ‌$n$ دارد و می‌تواند هر خانه از آن را با یکی از حروف $)$ یا $($ پر کند. آقای الف به چند تا از زیربازه های این آرایه علاقه زیادی دارد و دوست دارد تا طوری آرایه را پر کند که هم کل آرایه و هم هر یک از زیربازه های موردعلاقه‌اش تشکیل یک پرانتز‌گذاری معتبر دهد. همچنین در $q$ مرحله در هر مرحله یک زیربازه به زیربازه های مورد‌علاقه آقای الف اضافه می‌شود. به‌ازای حالت ابتدایی و بعد از هر یک از مراحل به آقای الف بگویید که به چند طریق می‌تواند این کار را انجام دهد؟

در خط اول دو عدد $n$ و $m$ می‌آید که به ترتیب نمایانگر طول آرایه و تعداد زیربازه های موردعلاقه اولیه است.

در $m$ خط بعدی در هر خط دو عدد $l_i$ و $r_i$ می‌آید. تضمین می‌شود $[l_1, r_1] = [1, n]$

در خط بعدی عدد $q$ می‌آید.

در $q$ خط بعدی در هر خط دو عدد $l'_j$ و $r'_j$ می‌آید.

خروجی شامل $q+1$ خط است. در خط اول جواب را به ازای بازه های مورد‌علاقه اولیه و در $q$ خط بعدی، جواب را پس از اضافه کردن هر بازه مورد‌علاقه جدید خروجی دهید. خروجی را به پیمانه‌ی $10^9+7$ چاپ کنید.

• زیرمسئله اول (۳ نمره): $n \leq 16, m, q \leq 18$.
• زیرمسئله دوم (۱۲ نمره): $n \leq 1000, m \leq 500, q = 0$.
• زیرمسئله سوم (۲۶ نمره): $q = 0$.
• زیرمسئله چهارم (۲۳ نمره): جمع طول $q$ بازه ای که اضافه می‌شوند حداکثر $10^6$ است
• زیرمسئله پنجم (۳۶ نمره): بدون محدودیت اضافی.

• $1 \le n \le 4 \times 10^5$
• $1 \le m \le 2 \times 10^5$
• $0 \le q \le 2 \times 10^5$
• $1 \le m + q \le 2 \times 10^5 + 5$
• $1 \le l_i \le r_i \le n$
• $1 \le l'_j \le r'_j\le n$
• $l_1 = 1, r_1 = n$