D. Левко ба Олонлогууд

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Левко бүх төрлийн олонлогуудад дуртай.

Левкод бүхэл тоон $a_1,a_2,... ,a_n$ ба $b_1,b_2,... ,b_m$ цуваанууд ба $p$ анхны тоо өгөгдсөн.Тэр өнөөдөр n ширхэг олонлог үүсгэж байгаа. $i$-дэх олонлог үүсэх үйл явцыг дараах байдлаар тодорхойлъё:

  1. Эхлээд энэ нь дан ганц 1 гэсэн элементтэй байна.
  2. Энэ олонлогоосоо дурын $c$ тоо авъя. $j (1\le j\le m)$ бүрийн хувьд $(c·a_i^{b_j}) mod p$ тоо энэ олонлогт байхгүй байвал олонлогт нэмнэ.
  3. Бид олонлогт тоо нэмж чадахгүй болох хүртэл 2-р алхмыг үргэлжлүүлье. Левко хэдэн ширхэг ядахнаа нэг олонлогт харьяалагдаж байгааг мэдэхийг хүсчээ. Өөрөөр хэлбэл энэ олонлогуудын нэгдэл хэчнээн элементтэйг тэр мэдэхийг хүсч байгаа.

Оролт

Эхний мөр $n, m, p (1\le n\le 104, 1\le m\le 10^5, 2 ≤p≤10^9)$ тоонууд агуулна.($p$ анхны тоо)

2 дахь мөр $a_1,a_2,... ,a_n (1\le a_i

Гаралт

Олонлогуудын хэчнээн элементтэйг илтгэх ганц тоог хэвлэ.

Орчуулсан: Төрбат

Жишээ тэстүүд

Оролт
1 1 7
2
5
Гаралт
3
Оролт
1 2 7
2
2 4
Гаралт
3
Оролт
2 1 7
1 6
2
Гаралт
1
Оролт
2 1 7
1 6
5
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...