Kostya and Ignat love numbers as gifts, but they almost always start arguing when they receive two numbers that are coprime (i.e., their greatest common divisor is 1) at the same time.

Vadim decided to cheer them up and give them a gift on the same day. For this occasion, he has an array of N numbers that has been sitting on the top shelf, but his access to it is very limited. On some days, he can only access numbers from the subarray [l, r], and on other days, he has no access at all, during which the number at position p changes to some other number.

For each day when Vadim has access, he wants to find a pair of numbers that he can gift to Kostya and Ignat, or determine that such a pair does not exist. Your task is to help him with this challenging task.

The first line contains two integers N and Q — the number of numbers in the array and the number of interesting days (2 ≤ N ≤ 10⁵, 1 ≤ Q ≤ 10⁵).

The second line contains N integers a_i — all elements of the array before the start of the interesting days (2 ≤ a_i ≤ 10⁶).

The following Q lines describe the interesting days in one of the following formats:

For each day when access to the subarray is available, output -1 if no pair of non-coprime numbers can be found, or two different positions belonging to the given subarray where two non-coprime numbers are located.

If there are multiple answers, output any.