Ալգորիթմներ և Տվյալների Կառուցվածքներ

Մեկ էլեմենտի հեռացում 2

Տրված է n ամբողջ թվերից բաղկացած մի ցանկ։ Ձեզ խնդրում են հեռացնել այդ ցանկից որևէ մեկ թիվ այնպես, որ մնացած բոլոր թվերի արտադրյալի m-ի վրա բաժանելիս ստացվող մնացորդը հավասար լինի p-ի: Ավելի ֆորմալ ձևակերպված, եթե հեռացված էլեմենտը գտնվում է r դիրքում, ապա.

(a1⋅a2⋅...⋅ar−1⋅ar+1⋅...⋅an)mod  m=p(a_1 \cdot a_2 \cdot ... \cdot a_{r-1} \cdot a_{r+1} \cdot ... \cdot a_n) \mod m = p

Ծրագիրը պետք է գտնի այդ էլեմենտի ինդեքսը կամ տպի Impossible, եթե նման թիվ չի գտնվում:

Մուտք

Մուտքի առաջին տողում տրված են 3 ամբողջ թվեր n (1 ≤ n ≤ 10510^5), m (1 ≤ m ≤ 10910^9) և p (0 ≤ p < m)։

Երկրորդ տողում տրված են n բացատներով բաժանված ամբողջ թվեր a1,a2,...,ana_1, a_2, ..., a_n (0 ≤ aia_i ≤ 10910^9)։

Ելք

Եթե նման թիվ գոյություն չունի, պետք է տպել Impossible, իսկ հակառակ դեպքում՝ վերոնշյալ թվի ամենափոքր հնարավոր ինդեքսը (ինդեքսավորումը սկսվում է 1-ից)։

Օրինակներ

Մուտք

Ելք

3 8 5
5 0 9

2

3 8 5
5 10 7

Impossible

Բացատրություն

  1. 5 * 9 = 45, իսկ 45 mod 8 = 5։ Այսինքն, երբ հեռացնում ենք 0 արժեքով էլեմենտը (ինդեքս 2), ստացված արտադրյալի մնացորդը հավասար է 5-ի։

  2. Երկրորդ օրինակում պարզապես հնարավոր չէ հեռացնել որևէ թիվ, որպեսզի մնացած արտադրյալի 8-ի բաժանելիս ստացվող մնացորդը 5 լինի, ուստի պատասխանը Impossible է։

Constraints

Time limit: 1.6 seconds

Memory limit: 512 MB

Output limit: 1 MB