LOVERS - Người Tình
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 3.0 giây
Giới hạn bộ nhớ: 256 megabyte
Đăng bởi: ami

Ami tặng LN một dãy số nhân ngày lễ tình nhân. Dãy số gồm n phần tử nguyên dương được đánh số từ 1. LN chê món quà của Ami và đem dãy số này thách thức cậu. Cụ thể, LN quyết định tàn phá món quà nhỏ của Ami bằng cách thay đổi giá trị của một vài phần tử, sau đó lấy ra một vị trí i bất kì, và đánh đố Ami rằng vị trí j gần i nhất mà gcd(Ai , Aj) > 1 là ở đâu ? gcd(a,b) là một số nguyên x lớn nhất mà a và b cùng chia hết cho x.

Dữ liệu vào

Dòng đầu tiên gồm 2 số n và q lần lượt là độ dài dãy số và số lần LN tàn phá dãy số (n,q <= 105).

Dòng thứ 2 là n số nguyên dương a1, a a3, ..., alần lượt là các phần tử của dãy số (ai <= 105).

q dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương i , x , k (i , k <= n , x <= 105) với ý nghĩa LN sẽ thay đổi phần tử ai thành x, và SAU ĐÓ hỏi Ami xem, số j gần k nhất để gcd(aj, ak) > 1.

Dữ liệu ra

q dòng, mỗi dòng là khoảng cách ngắn nhất tương ứng của một lần LN tàn phá và đánh đố Ami. Nếu không tồn tại j thoả mãn, in ra -1.

Ví dụ

Input

5 3

1 2 3 4 5

1 2 1

2 3 1

3 11 3

Output

1

3

-1

Giải thích

Sau lần đầu tiên LN tàn phá, dãy số thành 2 2 3 4 5. Số gần phần tử đầu tiên nhất và có ước chung lớn nhất với nó > 1 là phần tử thứ 2. gcd(2,2) = 2 > 1. Do đó in ra (2-1) = 1.

Sau lần thứ 2 LN tàn phá, dãy số thành 2 3 3 4 5. Số gần phần tử đầu tiên nhất và có ước chung lớn nhất với nó > 1 là phần tử thứ 4. gcd(2,4) = 2 > 1. Do đó in ra (4-1) = 3.

Sau lần đầu tiên LN tàn phá, dãy số thành 2 3 11 4 5. Không có phần tử nào có ước chung lớn nhất với 11 lớn hơn 1. Do đó in ra -1.

Back to Top