8. Ako prežiť domáce úlohy

Diktáty, testy, vyvolávanie, písomky, skúšky, projekty, prezentácie, prerátavanie, príklady, prosím, už stačilo.

Ale škole je to málo. Tu máš, milý Samo, zabalím ti školu na doma, aby si sa nenudil! To Samovi už len chýbalo - domáce úlohy. Je síce šikovný, a žiadna z nich mu nezaberá dlho, ale takú hromadu úloh naposledy videl keď objavil archív KSP.

No čo už, akademický úspech je nadovšetko, všetky domáce úlohy poslušne vypracuje. Niektoré ešte v škole ¹, niektoré doma. Keď príde domov, chcel by si však najskôr pár hodín zahrať najnovšiu hitovú videohru: Kosperova Brána 3. To by mu však rodičia museli dovoliť. Jeho tatko po ňom vždy chce, aby mal hotový nejaký počet úloh. Jeho mamka zasa vždy vyžaduje, aby mal hotovú polovicu práce (pozor, nie polovicu úloh).

Spísal si teda počas obednej prestávky² zoznam úloh v poradí, v ktorom ich plánuje vypracovať, a pripísal k nim aj koľko minút každá úloha trvá.

Počas telocviku zbiera od spolužiakov názory na dĺžku trvania jednotlivých úloh. Zároveň sa snaží podľa počasia vyhodnotiť, akú dobrú bude mať tatko náladu, a koľko hotových úloh od neho bude chcieť. Možno bude Samo musieť prepísať svoj zoznam…

Úloha

Samo má \(n\) domácich úloh. Keďže je šikovný, každá úloha mu trvá jednu, dve, alebo tri minúty.

Počas telocviku má \(q\) rozhovorov so spolužiakmi. Každý rozhovor spôsobí, že prehodnotí trvanie jednej úlohy. Vzápäťí Samo vyhodnotí, že jeho tatko od neho bude chcieť nejaký počet vypracovaných úloh \(x\).

Aby uspokojil oboch rodičov, bude musieť preusporiadať svoj pripravený zoznam úloh tak, aby prvých \(x\) úloh zaberalo presne polovicu času, čo zaberajú všetky úlohy. Preusporiadať ho môže len tak, že niekoľko krát vymení pozície dvoch (nie nutne susediacich) úloh v zozname.

Pomôžte Samovi, a po každom rozhovore a usúdení tatkovej nálady mu skontrolujte, koľko najmenej zmien by musel vo svojom zozname robiť.

Formát vstupu

V prvom riadku vstupu je číslo \(t\) - počet školských dní, v ktorých bude Samo musieť robiť domáce úlohy.

Nasleduje \(t\) popisov jednotlivých dní.

Popis ďna začína riadkom s číslami \(n\) a \(q\), udávajúce počet domácich úloh a počet rozhovorov.

V druhom riadku popisu je \(n\) čísel \(u_1, \cdots, u_n\) - dĺžky jednotlivých úloh, v poradí v akom ich má Samo v zozname.

Potom nasleduje \(q\) riadkov. V \(i\)-tom z nich sú tri čísla \(a_i\), \(b_i\) a \(x_i\), znázorňujúce že Samo prehodnotil trvanie \(a_i\) tej úlohy na \(b_i\) minút, a odhaduje že tatko po ňom bude chcieť aby mal hotových \(x_i\) úloh. Dĺžky úloh sa naozaj zmenia (Samo si ich prepíše v zozname), a ostávajú zmenené aj do budúcna (pokiaľ sa dĺžka opätovne nezmení nejakým neskorším rozhovorom).

Platí \(1 \leq t \leq 100\), \(1 \leq n, q\), \(1 \leq u_i, b_i \leq 3\) a \(1 \leq a_i, x_i \leq n\).

V jednotlivých sadách platia nasledujúce obmedzenia:

V druhej sade navyše platí, že \(x_i = \frac{n}{2}\) (zaokrúhlené nahor).

V tretej sade navyše platí, že dĺžky úloh sa nemenia (\(b_i\) bude rovné dĺžke úlohy \(a_i\)).

Formát výstupu

Pre každý deň, po \(i\)-tom rozhovore vypíšte jedno číslo - najmenší počet zmien, ktoré by Samo musel urobiť v svojom zozname, aby súčet dĺžok prvých \(x_i\) úloh bol rovný súčtu dĺžok všetkých zvyšných. Ak to Samo nevie dosiahnuť, vypíšte namiesto toho \(-1\).

Pripomíname, že zmena je vymenenie poradia dvoch (nie nutne susediacich) úloh v zozname, a Samo tieto zmeny počas telocviku reálne nevykonáva.

Príklady

Input:

2
8 5
1 1 2 3 1 2 3 1
4 1 4
7 1 4
7 1 3
5 2 5
6 1 5
1 1
2
1 1 1

Output:

1
0
1
-1
2
-1

Zoznam dĺžok úloh vyzeral po jednotlivých rozhovoroch nasledovne
1 1 2 3 1 2 3 1 (začiatok)
1 1 2 1 1 2 3 1
1 1 2 1 1 2 1 1
1 1 2 1 1 2 1 1
1 1 2 1 2 2 1 1
1 1 2 1 2 1 1 1
Po prvom rozhovore trvali úlohy dokopy 12 minút. Aby prvé štyri trvali toľko koľko zvyšné, mohol by Samo jednou zmenou vymeniť štvrtú a šiestu. Po druhom rozhovore trvajú prvé štyri úlohy toľko, čo posledné štyri, nemusel by teda robiť žiadne zmeny. Po piatom rozhovore môže vymeniť napríklad tretiu úlohu so šiestou a piatu so siedmou. Trvanie prvých piatich a zvyšných troch je potom rovnaké.

Input:

2
10 3
1 2 3 2 2 1 2 3 2 2
3 1 5
8 2 5
1 2 5
3 2
1 1 2
1 2 2
3 3 2

Output:

1
-1
0
-1
0

Príklad vstupu druhej sady

Input:

2
10 3
1 2 3 2 2 1 2 3 2 2
3 3 3
8 3 6
1 1 5
3 2
1 2 1
1 1 1
2 2 2

Output:

-1
1
0
1
1

Príklad vstupu tretej sady