Ճագարներ
Ֆերմեր Ջիվանը ճագարներ է բուծում։ Ճագարները սովորական չեն, շատ արագ են բազմանում։ Ամեն ամիս նրանց քանակը կրկնապատկվում է։ Սկզբնական պահին ֆերմեր Ջիվանն ունի
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 ճագարանոց։
Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակը
- Ենթախնդիր 1 (23 միավոր)
N ≤ 1000, M ≤ 1000, b[i] ≤ 5
- Ենթախնդիր 2 (22 միավոր)
N ≤ 1000, M ≤ 1000, C ≤ 100, b[i] ≤ 100
- Ենթախնդիր 3 (17 միավոր)
b[i] ≤ 100
- Ենթախնդիր 4 (17 միավոր)
C ≤ 100
- Ենթախնդիր 5 (21 միավոր) Լրացուցիչ սահմանափակումներ չկան։
Constraints
Time limit: 20 seconds
Memory limit: 512 MB
Output limit: 1 MB