Rick gave Morty an array A of N integers. Now, Rick wants Morty to solve his queries as quickly as possible. If Morty doesn't solve these queries on time, Rick will convert Morty into a Pickle. Morty is in great pain, Please help him as he doesn't know how to solve these queries.

Rick's queries are of the following two types:

1. Index Value: Multiply Value to A[Index] i.e. A[Index] = A[Index] ∗ Value 
2. Print an integer X such that the absolute difference between the following two values (A[1]∗A[2]∗.......∗A[X]) and (A[X+1]∗A[X+2]∗.......∗A[N]) is minimized. If there are multiple such values of X, then print the smallest one.

Input format

• First line: N that denotes the number of elements in the array and M that denotes the number of queries.
• Next line: N integers denoting the array.
• Next M lines: Queries of the two types.

Output format

• For each query of the second type, print the answer corresponding to the query.

Constraints

• 1 ≤ N, M ≤ 10⁵
• 1 ≤ A[i], Value ≤ 10¹⁸
• 1 ≤ Index ≤ N