Babel

• Ah, mă bucur așa de mult că în sfârșit am terminat de construit turnul ăsta.
• Có cây nào được tặng không? (Se dă un arbore?)
• Non ci viene dato un albero. (Nu ni se dă un arbore)

După ce Kushnezeu i-a demolat turnul, Matias nu se mai înțelegea cu semenii săi, așa că s-a decis să se joace singur. Are în fața lui un joc format din $N$ discuri de dimensiuni distincte, de la $1$ la $N$, așezate pe $3$ tije identice. Pe tot parcursul jocului, pe nicio tijă nu poate exista un disc de dimensiune mai mare așezat peste un disc de dimensiune mai mică. Cu alte cuvinte, ordinea dimensiunilor discurilor de pe fiecare tijă trebuie să fie strict descrescătoare, de la bază spre vârf. Se garantează că starea inițială a jocului respectă această regulă.

La o mutare, Matias poate lua un disc din vârful unei tije și să îl mute în vârful altei tije, doar dacă configurația care ar rezulta respectă regula de mai sus. Kushnezeu nu vrea să-l lase în pace, și decide că vrea și el să se joace. El își folosește puterea omnipotentă să materializeze pe tija $t$ toate discurile cu dimensiuni din intervalul $[l, r]$. Are grijă să le ordoneze descrescător și să le insereze corespunzător printre discurile aflate deja pe tijă, astfel încât să nu încalce regula de mai sus. Pentru configurația inițială și după efectuarea fiecărei astfel de operații transcendentale, îl întreabă pe Matias: "Care este numărul minim de mutări (modulo numărul meu favorit, $666 \ 013$) pentru a aduce toate discurile pe aceeași tijă?"

Cerință

Dată fiind configurația inițială a discurilor pe tije și toate operațiile lui Kushnezeu, ajutați-l pe Matias să răspundă corect la toate întrebările.

Date de intrare

Fișierul de intrare babel.in conține pe prima linie numerele naturale $N$ și $Q$, reprezentând numărul de discuri, respectiv numărul de operații ale lui Kushnezeu. Pe fiecare din următoarele $3$ linii se vor afla un număr natural $k_i$ reprezentând numărul de discuri aflate inițial pe tija $i$ și apoi $k_i$ numere, reprezentând dimensiunile discurilor aflate pe tija $i$, ordonate de la vârf către bază.

Pe următoarele $Q$ linii se află descrierile operațiilor lui Kushnezeu: pe a $i$-a linie se găsesc trei numere naturale $l_i$, $r_i$, $t_i$, reprezentând faptul că pentru a $i$-a operație Kushnezeu materializează toate discurile cu dimensiuni în intervalul $[l_i, r_i]$ pe tija $t_i$.

Date de ieșire

Fișierul de ieșire babel.out trebuie să conțină $Q + 1$ linii, a $i$-a dintre acestea conținând un număr natural reprezentând răspunsul cerut de Kushnezeu după efectuarea primelor $i - 1$ operații. Întrucât numărul de mutări poate fi foarte mare, acesta trebuie afișat modulo $666 \ 013$.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$
• $0 \leq Q \leq 200 \ 000$
• $0 \leq k_i \leq N$ pentru $1 \leq i \leq 3$
• $k_1 + k_2 + k_3 = N$
• $1 \leq l_i \leq r_i \leq N$
• $1 \leq t_i \leq 3$

Exemplul 1

babel.in

3 2
2 1 3
1 2
0
1 1 3
1 2 1

babel.out

3
2
0

Explicație

Inițial discurile sunt așezate ca în primul desen de mai jos. Se observă că este nevoie de $3$ mutări $(1 \rightarrow 3,\ 2 \rightarrow 1,\ 1 \rightarrow 1)$ pentru a aduce toate discurile pe aceeași tijă.

După prima operație a lui {Kushnezeu}, sunt necesare $2$ operații $(2 \rightarrow 1,\ 1 \rightarrow 1)$.

După ultima operație, se observă că toate discurile sunt deja pe tija $1$, deci Matias nu trebuie să efectueze nicio mutare.

Stare inițială:

După prima operație a lui Kushnezeu (în care discul $1$ ajunge pe stiva $3$):

După a doua operație a lui Kushnezeu (în care discurile $1$ și $2$ ajung pe stiva $1$):