Микица ја на папиру записао један низ целих бројева, који је за њега био врло битан. У току једног поспремања своје собе, изгубио је папир на коме је био записан тај низ и сада не може никако да га нађе. Али остао је папир на коме су забележене неке информације о том низу. Те информације су облика: збир елемената низа од елемента са индексом \(p\) (односно од елемента на позицији \(p\)) до елемента са индексом \(k\) (односно елемента на позицији \(k\)) је позитиван (или негативан). Помозите Микици да на основу тих чињеница одреди један низ који задовољава те чињенице. Ако такав низ не постоји (може се десити да је Микица погрешио негде током рачунања), исписати одговарајућу поруку.

Опис улаза

У првом реду стандардног улаза се налази цео број \(T\) и он представља број низова које је замислио Микица. У наредним редовима се налази \(T\) блокова у којима су описани низови које је замислио Микица. У првом реду описа се налазе два цела броја \(n\) и \(m\). Број \(n\) представља број елемената у низу, а број \(m\) је број информација о низу које је Микица записао. Сваки од наредних \(m\) редова у блоку садржи три цела броја: \(p\), \(k\) и \(z\) (\(1\leq p\leq k\leq n\), \(z\in\{-1,1\}\)). Та три броја означавају да је збир елемената низа од елемента на позицији \(p\) до елемента на позицији \(k\) позитиван (ако је \(z=1\)), односно негативан (ако је \(z=-1\)).

Опис излаза

За сваки од \(T\) низова из улаза треба исписати одговор (оним редом у коме се налазе у улазу). Ако за неки опис низа не постоји низ који одговара опису, онда у једном реду исписати број \(-1\). Ако за неки опис низа постоји такав низ онда у једном реду излаза исписати број \(1\), а у наредном реду исписати елементе низа раздвојене размацима (елементи низа треба да буду цели бројеви чија апсолутна вредност није већа од \(10^9\)).

Примери

Пример 1

Улаз

1
3 2
1 2 1
2 3 -1

Излаз

1
-1 2 -3

Пример 2

Улаз

2
6 4
1 3 1
1 5 -1
6 6 -1
4 6 1
2 1
1 2 1

Излаз

-1
1
-1 2

Објашњење примера 1

Сабирањем одговарајућих елемената се лако проверава да су оба услова које је Микица записао испуњена.

Ограничења и подзадаци

• \(1\leq T \leq 4\);
• \(1\leq n \leq 10000\);
• \(1\leq m \leq 200000\);
• Елементи низа који је Микица записао су цели бројеви између \(-10^9\) и \(10^9\).

Тест примери су подељени у две дисјунктне групе:

• У 30% тест примера важи \(1\leq n \leq 15\).
• У осталим тест примерима нема додатних ограничења.