Ֆերմեր Ջիվանը ճագարներ է բուծում։ Ճագարները սովորական չեն, շատ արագ են բազմանում։ Ամեն ամիս նրանց քանակը կրկնապատկվում է։ Սկզբնական պահին ֆերմեր Ջիվանն ունի N (1 ≤ N ≤ 100000) ճագարանոց, որոնցից i-րդում կա ճագար։ Բայց յուրաքանչյուր ճագարանոց նախատեսված է մինչև C հատ ճագարի համար։ Այդ պատճառով յուրաքանչյուր ամսվա վերջին օրը Ֆերմեր Ջիվանը հաշվում է իր ճագարները, և եթե որևէ ճագարանոցում ճագարների թիվը մեծ է լինում C-ից, նա հիմնում է նոր ճագարանոց և ճագարների ճիշտ կեսին տեղափոխում այդտեղ։ (Պարզության համար համարենք, որ ամսվա վերջին և առաջին օրերին ճագարները չեն բազմանում)։
Տեսչական կոմիտեից երբեմն ստուգումներ են անցկացնում և հաշվում են ֆերմեր Ջիվանի ճագարանոցների քանակը։ Ստուգումներն արվում են բացառապես ամավա վերջին օրերին, երբ ֆերմեր Ջիվանը ավարտած է լինում նոր ճագարանոցներ ստեղծելու գործը, բայց ոչ ամեն ամիս։ Պահանջվում է գրել ծրագիր, պարզելու համար, արդյո՞ք տեսչական կոմիտեի ստացած թվերը ճիշտ են։ Այդ քանակները կարող են շատ մեծ լինել, պետք է արտածել -ի վրա բաժանելուց մնացորդները։
Մուտքային տվյալներ
Առաջին տողում տրված են N (1 ≤ N ≤ 100000), M (1 ≤ M ≤ 100000) և C(1 ≤ C ≤ ) թվերը, N-ը սկզբնական պահին ճագարանոցների քանակն է։ M-ը հարցումների քանակն է։ C-ն ճագարների առավելագույն քանակն է, որ պետք է լինի ամսվա առաջին օրը։
Երկրորդ տողում տրված են, C-ին չգերզանցող, N հատ թվեր, դրանք ճագարների սկզբնական a[i] (1 ≤ a[i] ≤ C) քանակներն են ։
Երրորդ տողում տրված են M հատ ոչ բացասական ամբողջ թվեր, տեսչական մարմնի ստուգման b[i] (1 ≤ b[i] ≤ ) ամիսները։ Այդ թվերը պարտադիր չէ, որ տրված լինեն աճման կարգով։
Ելքային տվյալներ
Ելքում պետք է արտածել M հատ թիվ՝ մուտքում տրված M թվերից յուրաքանչյուրի համար այդ ամսվա առաջին օրվա սկզբին ճագարանոցների քանակը, նույն հերթականությամբ, ինչպես տրված են մուտքային տվյալներում։ Այդ քանակները կարող են շատ մեծ լինել, պետք է արտածել -ի վրա բաժանելուց մնացորդները։
Օրինակ
Մուտք
Ելք
2 3 5
2 3
0
4
2
2
24
6
Օրինակի բացատրություն
Սկզբում, 0-րդ ամսին կա երկու ճագարանոց, մեկում 2 ճագար, մյուսում 3։ Առաջին ամսում նրանք կկրնապատկվեն, կդառնան 4 և 6։ Քանի որ առավելագույն քանակը 5 է, ֆերմեր Ջիվանը առաջին ամսվա վերջին օրը կստեղծի 3-րդ ճագարանոցը, և կկիսի եկրորդի ճագարներին, կստացվի 4, 3, 3: Երկրորդ ամսում նրանց քանակը կդառնա 8, 6, 6 և ֆերմերը կստեղծի ևս 3 ճագարանոց, կունենա՝ 4, 4, 3, 3, 3, 3: Երրորդ ամսվա վերջում նա կունենա 12 ճագարանոց, որոնցից 4-ում կլինեն 4-ական ճագար, իսկ 8-ում՝ 3-ական։ Իսկ 4-րդ ամսվա վերջին օրը նա արդեն կունենա 24 ճագարանոց։