Žemlja

Znanstvenici su u udaljenoj galaksiji otkrili planet Žemlja. Za razliku od našeg planeta, Žemlja je ravna ploča. Također, za razliku od našeg planeta, tamo se razina vode spušta umjesto da raste. Planet možemo zamisliti kao ploču (matricu) sa N redaka i 3 stupca. Na početku su sva polja poplavljena, tj. neprohodna. Promatramo planet kroz Q dana. Svaki dan jedno polje postane prohodno (više nije poplavljeno). Na kraju svakog dana, naše znanstvenike zanima koliko je istovremeno najviše disjunktnih puteva koji prolaze prohodnim poljima moguće načiniti, tako da svaki put počinje u prvom stupcu, a završava u zadnjem. Kretanje je dozvoljeno u 4 smjera.

Ulazni podatci

Prvi redak sadrži prirodne brojeve N i Q, veličina planeta te broj dana. Sljedećih Q redaka sadrže po dva cijela broja: xi (1 ≤ xi ≤ N ) i yi (1 ≤ yi ≤ 3), koji označuju redak i stupac polja koje je postalo prohodno i-ti dan. Svako od Q polja je međusobno različito.

Izlazni podatci

Ispišite Q redaka. U i-tom retku ispišite najveći mogući broj puteva nakon i dana.

Bodovanje

U svim testnim primjerima vrijedit će 1 ≤ Q ≤ 3 · N

Podzadatak Bodovi Ograničenja

1 15 1 ≤ N ≤ 3 000 2 8 1 ≤ N ≤ 200 000, N ≤ Q, prvih N dana su polja u prvom stupcu 2 6 1 ≤ N ≤ 200 000, poplavljena polja su sortirana po retku pa po stupcu 2 6 1 ≤ N ≤ 200 000, poplavljena pola su sortirana po stupcu pa po retku 3 55 1 ≤ N ≤ 200 000

Probni primjeri

ulaz ulaz ulaz 3 7 3 7 4 12 1 2 1 3 4 1 3 3 2 2 1 3 2 2 3 3 4 2 3 2 3 2 1 2 2 1 2 3 3 1 1 3 3 1 2 2 1 1 1 1 1 1 3 3 izlaz izlaz 3 2 0 0 4 3 0 0 2 1 0 0 2 3 0 0 izlaz 1 0 1 1 0 2 1 0 0 0 0 0 1 1 2 3 3 4