==Include(page="template/taskheader" task_id="bridge")==

==Include(page="template/raw")==
 

Fat-Frumos a plecat in cautarea iubirii sale, fiica imparatului, Simona, care a fost rapita de balaurul cel rau si dusa in pestera acestuia. Acesta s-a pregatit intens de lupta insa el nu a stiut ca balaurul ii pregatise o surpriza, si astfel l-a atras pe acesta pe un pod. Pe pod Fat-Frumos se poate deplasa pasind (se va deplasa o scandura la dreapta), sarind (se va deplasa $2$ scanduri la dreapta), stationand (va ramane pe aceeasi scandura) sau teleportandu-se (vezi scandura teleportoare). Insa podul este putin mai ciudat fiind format din $4$ tipuri de scanduri astfel:
* $0$ - scandura buna (pe o astfel de scandura se poate stationa, pasi, sari sau teleporta, si se poate ajunge oricum pe ea)

h2. Date de Intrare

Pe prima linie a fisierului $bridge.in$ vor fi scrise $2$ numere $N$ si $M$ reprezentand numarul de scanduri respective numarul de intrebari. Pe urmatoarea linie vor fi scrise N numere cuprinse intre $0$ si $3$ reprezentand configuratia podului, corespondenta fiind cea de mai sus. Pe urmatoarele linii vor fi scrise scandurile destinatie pentru fiecare scandura teleportoare in ordinea aparitiei acestora pe pod, si, in final, pe urmatoarele $M$ linii vor fi scrise cate $2$ numere $X$ si $K$ care definesc o intrebare de genul "In cate moduri se poate ajunge pe scandura $X$ in $K$ pasi?".

Pe prima linie a fisierului bridge.in vor fi scrise $2$ numere $N$ si $M$ reprezentand numarul de scanduri respective numarul de intrebari. Pe urmatoarea linie vor fi scrise N numere cuprinse intre $0$ si $3$ reprezentand configuratia podului, corespondenta fiind cea de mai sus. Pe urmatoarele linii vor fi scrise scandurile destinatie pentru fiecare scandura teleportoare in ordinea aparitiei acestora pe pod, si, in final, pe urmatoarele $M$ linii vor fi scrise cate $2$ numere $X$ si $K$ care definesc o intrebare de genul "In cate moduri se poate ajunge pe scandura $X$ in $K$ pasi?".

h2. Date de Iesire

==Include(page="template/taskfooter" task_id="bridge")==

1238