SPOJ in Armenian

Դիտարկենք k երկարությամբ 0 և 1 սիմվոլներով գրվող բոլոր տողերը: Գրեյի կոդը իրենից ներկայացնում է այդ տողերի այնպիսի հաջորդականություն, որում կամայական երկու հաջորդական տող իրարից տարբերվում են ուղիղ մեկ սիմվոլով: Հաջորդական են համարվում նաև առաջին և վերջին տողերը:

k =1 երկարությամբ Գրեյի կոդը հետևյալն է. 0, 1

k =2 երկարությամբ Գրեյի կոդը հետևյալն է.  00, 01, 11, 10

k երկարությամբ Գրեյի կոդից k+1 երկարությամբ Գրեյի կոդ ստանալու համար անհրաժեշտ է k երկարությամբ կոդը նույնությամբ արտագրել, այնուհետև, (2^k + 1)–րդ տողից մինչև 2^k+1-րդ տողերը լրացնել այնպես, որ (2^k + i)-րդ տողում գրված լինի (2^k - i + 1)-րդ տողը: Այնուհետև 1,…,2^k տողերին անհրաժեշտ է ձախից կցագրել 0, իսկ 2^k+1,..,2^k+1  տողերին անհրաժեշտ է ձախից կցագրել 1:

Անհրաժեշտ է գրել ծրագիր, որը պատասխանում է երկու տեսակի հարցման: Առաջին տիպի հարցման դեպքում տրված  n և k թվերի համար պետք է արտածել k երկարությամբ Գրեյի կոդի n-րդ տողը: Երկրորդ տիպի հարցման դեպքում տրված տողի համար անհրաժեշտ է արտածել իր կարգահամարը իր երկարությամբ Գրեյի կոդի մեջ:

Մուտքը

Առաջին տողում տրված է հարցումների T(1<=T<=100000) քանակը: Հաջորդ T տողերից յուրաքանչյուրը սկսվում է զրոյով կամ մեկով: Եթե հարցումը սկսվում է զրոյով, ապա այն առաջին տիպի է և զրոյին հաջորդում են n և k(1<=k<=30) բնական թվերը, հակառակ դեպքում այն երկրորդ տիպի է և մեկին հաջորդում է ինչ որ երկարությամբ Գրեյի կոդի որևէ տող: 

Ելքը

Անհրաժեշտ է արտածել T տող, i-րդ տողում պետք է լինի i-րդ հարցման պատասխանը (վերջին տողից հետո անհրաժեշտ է արտածել նոր տողի անցման սիմվոլ):

Օրինակ

Մուտքը.
5

0 1 1
0 2 1
1 1
0 6 3
1 111

Ելքը.
0

1

2

111

6

Հեղինակներ

Ռոբերտ Դավթյան և Հրայր Հարությունյան