Ատոմային ֆիզիկոս

Հրաչյան ֆիզիկոս է, ով կենտրոնացած է միջուկային հետազոտությունների և տարրական մասնիկների ֆիզիկայի վրա։

Այս պահին նա դիտարկում է մասնիկներ, որոնք հաջորդաբար դասավորված են իրար հետևից։ Յուրաքանչյուր մասնիկ ունի տեսակ, որը ներկայացված է -ից միջակայքում գտնվող բնական թվով։

Այս հետազոտության ընթացքում անհրաժեշտ է անցկացնել հատ փորձ։ -րդ փորձի ժամանակ դիտարկվում են բոլոր մասնիկները հաջորդականության -րդից մինչև -րդ դիրքերը ()։ Դիտարկվող մասնիկներից կարող ենք ընտրել երկու տարբեր տեսակի մասնիկներ և այնպես անել, որ դրանք բախվեն՝ առաջացնելով երկու մասնիկների ոչնչացում։

Այս բախման գործընթացը կրկնվում է, քանի դեռ դիտարկվող մասնիկների մեջ գոյություն ունեն տարբեր տեսակի մասնիկներ։

Փորձն ավարտվում է, եթե՝

Բոլոր դիտարկվող մասնիկները ոչնչանում են, կամ
Մնացած մասնիկները նույն տեսակի են։

Իհարկե, կախված այն բանից, թե որ մասնիկներն ենք ընտրում բախման համար և ինչ հերթականությամբ ենք դա անում, հնարավոր է ստանալ տարբեր արդյունքներ։

Քանի որ մասնիկների բախումը թանկարժեք գործընթաց է, Հրաչյան որոշել է փորձերը կատարել միայն տեսականորեն։ Ձեզ առաջադրված է, յուրաքանչյուր փորձի համար պարզել, թե քանի տարբեր տեսակ գոյություն ունի, այնպիսին, որ փորձի վերջում հնարավոր է, որ մնա մեկ կամ ավելի այդ տեսակի մասնիկ։

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

Առաջին տողը պարունակում է երկու բնական թիվ՝ և (), որոնք ներկայացնում են մասնիկների քանակը և փորձերի քանակը։

Երկրորդ տողը պարունակում է թիվ՝ (). մասնիկների տեսակները։

Յաջորդ տողերից յուրաքանչյուրը պարունակում է երկու բնական թիվ՝ և (). -րդ փորձում դիտարկվող մասնիկների միջակայքը։

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

փորձերից յուրաքանչյուրի համար արտածեք մեկ թիվ, որը ցույց է տալիս, թե քանի տարբեր տեսակի կարող է լինել վերջում մնացած մասնիկ(ներ)ը։ Յուրաքանչյուր արդյունք պետք է տպվի առանձին տողում։

Oրինակներ

Մուտք	Ելք
11 5 2 4 2 3 4 4 3 1 4 4 4 1 4 2 8 6 9 8 10 8 11	1 4 1 1 1

Oրինակի բացատրություն

Փորձ 1․ Կարող ենք բախեցնել և տեսակի մասնիկները, որի արդյունքում կմնան երկու տեսակի մասնիկներ։ Ուստի, միակ հնարավոր մնացած տեսակը -ն է։
Փորձ 2․ Վերջում կարող է մնալ ցանկացած տեսակի մասնիկ(ներ)։
Փորձեր 4 և 5․ Անկախ բախումների ընտրություններից, վերջնական մնացած մասնիկ(ներ)ը միշտ կլինի տեսակի։

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

Համար	Սահմանափակում	Միավոր
0	Օրինակ	0
1	բոլոր համար	13
2	Գոյություն ունի յուրաքանչյուր տեսակից առավելագույնը երկու մասնիկ	19
3		17
4		25
5	Լրացուցիչ սահմանափակումներ չկան	26

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 25 MB