You are given an array \(A\) of \(N\) integers. Now, you are required to process queries of the following two types.

\(pos\ val\): Multiply \(val\) to \(A[pos]\) i.e. \(A[pos]=A[pos]*val\)
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\le N, M \le 10^5\)

\(1 \le A[i], val \le 10^{18}\)

\(1\le pos \le N\)