Милош много воли да шири туђе тајне у школи. Јутрос је пре часова сазнао једну веома важну тајну и жели да сви сазнају за њу. Одлучио је да свима каже тајну у току часа. На часу сви ученици седе у једном реду. Милош ће рећи тајну ученику лево од себе(ако постоји) и ученику десно од себе (ако постоји). Затим ће ученик који седи лево од њега пренети ученику који седи још једно место у лево, а ученик који седи десно од њега ће рећи ученику који седи још једно место у десно. Ово ће се понављати све док се тајна не прошири до крајева реда. Међутим, постоје ученици који прате час и које не занимају туђе тајне. Они неће даље ширити тајну (иако можда не седе на крају реда).
Наставници се не свиђа што ученици причају на часу, па је направила неколико распореда седења. У свим распоредима седења ученици који прате наставу седе на истим местима, јер они не праве буку и њих не мора да премешта. Одредите колико ученика ће сазнати тајну за сваки распоред седења ако је познато где је наставница рекла Милошу да седи. Сложеност алгоритма треба бити О(r⋅logm).
Прва линија стандардног улаза садржи природан број n ≤ 109 који представља укупан број ученика.
Друга линија стандардног улаза садржи природан број m (m ≤ n и m ≤ 105) који представља број ученика који прате наставу.
У трећој линији стандардног улаза уноси се m бројева између 1 и n - редни бројеви места где седе ученици који прате наставу.
У четвртој линији стандардног улаза уноси се број r ≤ 105 - број распореда који је смислила наставница.
У наредних r линија стандардног улаза уноси се број између 1 и n - редни број места где у распореду седи Милош. Гарантује се да на овом месту не седи ученик који прати наставу из друге линије улаза.
На стандардни излаз у r редова исписати колико ученика је сазнало тајну.
10
3
1 4 7
2
2
92
3У првом распореду седења за тајну ће сазнати ученици који седе на местима 2 и 3. Ученици 1 и 4 прате на часу и неће даље ширити ову тајну. У другом распореду седења ученици 8,9 и 10 ће сазнати за тајну. Ученик 7 прати на часу, а ученик 10 седи на крају реда и нема коме другом да је каже.
1000
3
100 255 932
2
400
934676
68У првом распореду седења за тајну ће сазнати ученици који седе на местима која имају редне бројеве од 256 до 931 (укључујући та два). Ученици 255 и 932 прате на часу и неће даље ширити ову тајну. У другом распореду седења ученици који седе лево од ученика 932 ће сазнати за тајну. Ученик 932 прати на часу, а ученик 1000 седи на крају реда и нема коме другом да је каже.