Trên bảng, thầy giáo viết sẵn một dãy gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ và một số nguyên dương ~m~ (~m > 1~).

Một đoạn con gồm các phần tử liên tiếp ~a_l, a_{l+1}, \dots, a_r~ (~1 \le l \le r \le n~) được gọi là may mắn nếu tích của tất cả các số hạng trong đoạn chia hết cho ~m~, tức là: ~\left(\prod_{k=l}^r a_k\right) \ \vdots \ m~

Nhiệm vụ của bạn là xét từng vị trí ~i~ trong dãy (~1 \le i \le n~) và tìm độ dài của đoạn con may mắn ngắn nhất có chứa phần tử ~a_i~.

Yêu cầu: Với mỗi vị trí ~i~ (~1 \le i \le n~), hãy tìm cặp chỉ số ~(l, r)~ sao cho ~1 \le l \le i \le r \le n~ và tích ~a_l \cdot a_{l+1} \cdots a_r~ chia hết cho ~m~. Trong tất cả các cặp ~(l, r)~ thỏa mãn, hãy đưa ra giá trị nhỏ nhất của độ dài đoạn ~r - l + 1~. Nếu không tồn tại bất kỳ đoạn con may mắn nào chứa vị trí ~i~, in ra ~-1~.

Đầu vào (Input)

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ (~1 \le n \le 2 \cdot 10^5~, ~2 \le m \le 10^9~) lần lượt là số lượng phần tử của dãy và số nguyên ~m~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9~) biểu thị các phần tử của dãy.

Đầu ra (Output)

• In ra trên một dòng gồm ~n~ số nguyên cách nhau bởi dấu cách, trong đó số thứ ~i~ là độ dài của đoạn con may mắn ngắn nhất chứa vị trí ~i~. Nếu không tồn tại đoạn con thỏa mãn, in ra ~-1~.

Ví dụ (Examples)

Ví dụ 1

Input:

5 12
2 3 5 4 9

Output:

4 3 3 2 2

Giải thích: Dãy số ~a = [2, 3, 5, 4, 9]~ và ~m = 12~. Các đoạn con may mắn (có tích chia hết cho 12) gồm:

• Đoạn ~[1 \ldots 4]~ là ~[2, 3, 5, 4]~: tích ~= 2 \times 3 \times 5 \times 4 = 120~ (chia hết cho 12), độ dài ~= 4~.
• Đoạn ~[2 \ldots 4]~ là ~[3, 5, 4]~: tích ~= 3 \times 5 \times 4 = 60~ (chia hết cho 12), độ dài ~= 3~.
• Đoạn ~[4 \ldots 5]~ là ~[4, 9]~: tích ~= 4 \times 9 = 36~ (chia hết cho 12), độ dài ~= 2~.

Xét từng vị trí ~i~:

• ~i = 1~ (~a_1 = 2~): Đoạn may mắn ngắn nhất chứa ~a_1~ là ~[1 \ldots 4]~, độ dài ~4~.
• ~i = 2~ (~a_2 = 3~): Đoạn may mắn ngắn nhất chứa ~a_2~ là ~[2 \ldots 4]~, độ dài ~3~.
• ~i = 3~ (~a_3 = 5~): Đoạn may mắn ngắn nhất chứa ~a_3~ là ~[2 \ldots 4]~, độ dài ~3~.
• ~i = 4~ (~a_4 = 4~): Đoạn may mắn ngắn nhất chứa ~a_4~ là ~[4 \ldots 5]~, độ dài ~2~.
• ~i = 5~ (~a_5 = 9~): Đoạn may mắn ngắn nhất chứa ~a_5~ là ~[4 \ldots 5]~, độ dài ~2~.

Kết quả đưa ra: 4 3 3 2 2.

Ví dụ 2

Input:

4 18
2 3 5 7

Output:

-1 -1 -1 -1

Giải thích: Tích của toàn bộ dãy số là ~2 \times 3 \times 5 \times 7 = 210~, không chia hết cho ~18~ (vì chỉ có một thừa số 3, trong khi ~18 = 2 \times 3^2~). Do đó không tồn tại bất kỳ đoạn con may mắn nào trong cả dãy, in ra -1 -1 -1 -1.

Chấm điểm (Scoring)