Բեզոարյան այծ

Բեզոարյան այծը որոշել է ճանապարհորդել Հայաստանի մի ծայրից մյուս ծայրը, սակայն իմանալով, որ Հայաստանը շատ լեռնային երկիր է և Հայաստանի տեղանքի մի քանի մաս ուսումնասիրելուց հետո, նա կցանկանար իմանալ թե տեսականորեն քանի տարբեր տեսակի ճանապարհներով նա կարող է անցնել, դրա համար նրան հարկավոր է լուծել հետևյալ խնդիրը.

Հաշվել կարգի տեղափոխությունների ( կարգի տեղափոխություն է կոչվում -ից թվերի որևէ դասավորություն, առանց կրկնությունների, օրինակ՝ -ը -րդ կարգի տեղափոխություն է) քանակը, որոնք համապատասխանում են հետևյալ տիպի սահմանափակումների.

-ից ձգվող ենթազանգվածը հովիտ է։
-ից ձգվող ենթազանգվածը սար է։

Զանգվածը կոչվում է`

Հովիտ, եթե խիստ նվազում է, ապա խիստ աճում, օրինակ՝ -ը հովիտ է։
Սար, եթե խիստ աճում է, ապա խիստ նվազում, օրինակ` -ը սար է։

Խիստ նվազող կամ աճող ենթազանգվածը ո’չ հովիտ է, ո’չ էլ սար։

Օգնեք բեզոարյան այծին լուծել այս խնդիրը։

Մուտքային տվյալներ

Առաջին տողը պարունակում է մեկ թիվ՝ , թեստերի քանակը։

Ամեն թեստի նկարագրություն ունի հետևյալ տեսքը.

Առաջին տողում տրված են երկու թիվ՝ և , համապատասխանաբար տեղափոխությունների կարգը և սահմանափակումների քանակը։

Հաջորդ M տողերից ամեն մեկում տրված է 3 թիվ՝ , և ()։ -ը և -ը ցուց են տալիս ենթազանգվածը, իսկ -ը ցույց է տալիս, թե այն ինչ պետք է լինի, -ը նշանակում է հովիտ, իսկ -ը սար։

Երաշխավորվում է, որ բոլոր թեստերի -երի գումարը չի գերազանցում -ը և բոլոր թեստերի -երի գումարը չի գերազանցում -ը։

Ելքային տվյալներ

Ամեն թեստի համար պետք է արտածել մեկ թիվ՝ սահմանափակումներին համապատասխանող տեղափոխությունների քանակի մնացորդը -ի վրա։

Օրինակ

Մուտք	Ելք
4 3 1 1 3 2 3 1 1 3 1 7 9 3 7 2 1 5 1 2 6 1 1 6 1 1 4 1 2 5 1 4 7 2 5 7 2 2 4 1 4 2 1 4 2 1 3 2	2 2 55 3

Ենթախնդիրներ

-ով նշանակենք մեկ թեստի ենթաթեստերում -երի գումարը, -ով՝ -երի։

Համար	Սահմանափակում	Միավոր
0	Օրինակը	0
1		10
2		15
3		15
4	, գոյություն ունեն միայն առաջին տիպի սահմանափակումներ, այսինքն բոլոր սահամանափակումների համար	20
5		20
6	Լրացուցիչ սահմանափակումներ չկան	20

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB