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\)
For First Query :Initially the answer is 4 since 4 is the smallest index which divides the array into 2 halves having product of first part as 2*2*2*2=16 and product of second part as 2*2*2*2=16.So the value abs(16-16)=0, which is smallest possible.
Second Query : The array changes to 2 2 4 2 2 2 2 2
If we choose index 3, then the product of first part will be 2*2*4=16 and product of second part will be 2*2*2*2*2=32, the value abs(16-32)= 16 and if we choose index 4, then the product of first part will be 2*2*4*2=32 and product of second part will be 2*2*2*2=16, the value abs(32-16)= 16. Since 3 is the smaller index among 3 and 4 so answer is 3.
