Մեկ էլեմենտի հեռացում 2
Փաստորեն, տրված է n ամբողջ թվերից բաղկացած մի ցանկ։ Առաջադրանքը կայանում է նրանում, որ պետք է հեռացնել այդ ցանկից որևէ մեկ թիվ այնպես, որ մնացած բոլոր թվերի արտադրյալի m-ով վերցրած մնացորդը հավասար լինի p-ի: Ավելի формալ ձևով, եթե հեռացված էլեմենտը գտնվում է r ինդեքսում, ապա
Ծրագիրը պետք է գտնի այդ էլեմենտի ինդեքսը կամ տպի
Impossible, եթե նման թիվ չի գտնվում:Մուտք
Մուտքի առաջին տողում տրված են 3 ամբողջ թվեր
n (1 ≤ n ≤ 10^5), m (1 ≤ m ≤ 10^9) և p (0 ≤ p < m)։Երկրորդ տողում տրված են
n բացատներով բաժանված ամբողջ թվեր a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^9)։Ելք
Եթե նման թիվ գոյություն չունի, պետք է տպել
Impossible, իսկ հակառակ դեպքում՝ վերոնշյալ թվի ամենափոքր ինդեքսը շարքում (ինդեքսավորումը սկսվում է 1-ից)։Օրինակներ
Մուտք | Ելք |
3 8 5
5 0 9 | 2 |
3 8 5
5 10 7 | Impossible |
Բացատրություն
- 5 * 9 = 45, իսկ 45 mod 8 = 5։ Այսինքն, երբ հեռացնում ենք 0 արժեքով էլեմենտը (ինդեքս 2), ստացված արտադրյալի մնացորդը հավասար է 5-ի։
- Երկրորդ օրինակում պարզապես հնարավոր չէ հեռացնել որևէ թիվ, որպեսզի մնացած արտադրյալի 8-ով վերցրած մնացորդը դառնա 5, ուստի պատասխանը
Impossibleէ։
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB