Problem: Nastya likes reading and even spends whole days in a library sometimes. Today she found a chronicle of Byteland in the library, and it stated that there lived shamans long time ago. It is known that at every moment there was exactly one shaman in Byteland, and there were n shamans in total enumerated with integers from 1 to n in the order they lived. Also, each shaman had a magic power which can now be expressed as an integer.

The chronicle includes a list of powers of the n shamans. Also, some shamans can be king-shamans, if they gathered all the power of their predecessors, i.e. their power is exactly the sum of powers of all previous shamans. Nastya is interested in whether there was at least one king-shaman in Byteland.

Unfortunately many of the powers are unreadable in the list, so Nastya is doing the following:

  * Initially she supposes some power for each shaman. 
  * After that she changes the power of some shaman q times (the shamans can differ) and after that wants to check if there is at least one king-shaman in the list. If yes, she wants to know the index of any king-shaman. 



Unfortunately the list is too large and Nastya wants you to help her.

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 2·105).

The second line contains n integers a1, ..., an (0 ≤ ai ≤ 109), where ai is the magic power of the i-th shaman.

After that q lines follow, the i-th of them contains two integers pi and xi (1 ≤ pi ≤ n, 0 ≤ xi ≤ 109) that mean that the new power of the pi-th shaman is xi.

Output

Print q lines, the i-th of them should contain  - 1, if after the i-th change there are no shaman-kings, and otherwise a single integer j, where j is an index of some king-shaman after the i-th change.

If there are multiple king-shamans after each change, print the index of any of them.

Examples

Input

2 1
1 3
1 2


Output

-1


Input

3 4
2 2 3
1 1
1 2
2 4
3 6


Output

3
2
-1
3


Input

10 7
0 3 1 4 6 2 7 8 10 1
2 5
1 3
9 36
4 10
4 9
1 2
1 0


Output

1
-1
9
-1
4
-1
1

Note

In the first example powers of shamans after the first change are equal to (2, 3). The answer equals  - 1, because the sum of powers of shamans before the first shaman is equal to 0, and before the second is equal to 2.

In the second example after the first change the powers are equal to (1, 2, 3). The answer is equal to 3, because the power of the third shaman is equal to 3, and the sum of powers of the first and the second shaman is also 1 + 2 = 3. After the second change the powers become equal to (2, 2, 3), where the answer equals 2. After the third change the powers become equal to (2, 4, 3), where the answer equals  - 1. After the fourth change the powers become equal to (2, 4, 6), where the answer equals 3.

Solution (in JAVA):

Solution:
/*
Keep solving problems.
*/

import java.util.*;
import java.io.*;

public class CFG {
    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    private static final long MOD = 1000 * 1000 * 1000 + 7;
    private static final int[] dx = {0, -1, 0, 1};
    private static final int[] dy = {1, 0, -1, 0};
    private static final String yes = "Yes";
    private static final String no = "No";

    long[] arr;
    long[] sumTree;
    int[] maxTree;

    void build_tree(int node, int nodeStartIndex, int nodeEndIndex) {
        if(nodeStartIndex > nodeEndIndex) return; // Out of range
        if(nodeStartIndex == nodeEndIndex) { // Leaf node
            sumTree[node] = arr[nodeStartIndex]; // Init value
            maxTree[node] = nodeStartIndex;
            return;
        }

        build_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2); // Init left child
        build_tree(node * 2 + 1, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex); // Init right child
        sumTree[node] = sumTree[node * 2] +  sumTree[node * 2 + 1]; // Init root value
        if (arr[maxTree[node * 2]] <= arr[maxTree[node * 2 + 1]]) {
            maxTree[node] = maxTree[node * 2 + 1];
        }
        else {
            maxTree[node] = maxTree[node * 2];
        }
    }

    /**
     * Increment elements at queryIndex with value
     */
    void update_sum_tree(int node, int nodeStartIndex, int nodeEndIndex, int queryIndex, long value) {
        if(nodeStartIndex > nodeEndIndex || nodeStartIndex > queryIndex || nodeEndIndex < queryIndex) // Current segment is not within range [i, j]
            return;
        if(nodeStartIndex == nodeEndIndex) { // Segment is fully within range
            sumTree[node] += value;
            return;
        }

        update_sum_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryIndex, value); // Updating left child
        update_sum_tree(node * 2 + 1, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryIndex, value); // Updating right child

        sumTree[node] = sumTree[node * 2] + sumTree[node * 2 + 1]; // Updating root
    }

    /**
     * Increment elements at queryIndex with value
     */
    void update_max_tree(int node, int nodeStartIndex, int nodeEndIndex, int queryIndex, long value) {
        if(nodeStartIndex > nodeEndIndex || nodeStartIndex > queryIndex || nodeEndIndex < queryIndex) // Current segment is not within range [i, j]
            return;
        if(nodeStartIndex == nodeEndIndex) { // Segment is fully within range
            arr[queryIndex] = value;
            maxTree[node] = queryIndex;
            return;
        }

        update_max_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryIndex, value); // Updating left child
        update_max_tree(node * 2 + 1, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryIndex, value); // Updating right child
        if (arr[maxTree[node * 2]] <= arr[maxTree[node * 2 + 1]]) {
            maxTree[node] = maxTree[node * 2 + 1];
        }
        else {
            maxTree[node] = maxTree[node * 2];
        }
    }

    /**
     * Query tree to get max element value within range [queryStartIndex, queryEndIndex]
     */
    long query_sum_tree(int node, int nodeStartIndex, int nodeEndIndex, int queryStartIndex, int queryEndIndex) {
        if(nodeStartIndex > nodeEndIndex || nodeStartIndex > queryEndIndex || nodeEndIndex < queryStartIndex) {
            return 0; // Out of range!!! change if necessary
        }

        if(nodeStartIndex >= queryStartIndex && nodeEndIndex <= queryEndIndex) {// Current segment is totally within range [i, j]
            return sumTree[node];
        }

        long q1 = query_sum_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryStartIndex, queryEndIndex); // Query left child
        long q2 = query_sum_tree(1 + node * 2, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryStartIndex, queryEndIndex); // Query right child

        return q1 + q2;
    }

    int query_max_tree(int node, int nodeStartIndex, int nodeEndIndex, int queryStartIndex, int queryEndIndex, long value) {
        if(nodeStartIndex > nodeEndIndex || nodeStartIndex > queryEndIndex || nodeEndIndex < queryStartIndex) {
            return n; // Out of range!!! change if necessary
        }

        if (arr[maxTree[node]] < value) {
            return n;
        }

        if(nodeStartIndex == nodeEndIndex) {// Current segment is totally within range [i, j]
            if (arr[maxTree[node]] >= value) {
                return maxTree[node];
            }
            else {
                return n;
            }
        }


        int q1 = query_max_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryStartIndex, queryEndIndex, value); // Query left child
        if (q1 != n && arr[q1] >= value) {
            return q1;
        }

        int q2 = query_max_tree(1 + node * 2, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryStartIndex, queryEndIndex, value); // Query right child
        if (q2 != n && arr[q2] >= value) {
            return q2;
        }
        return n;
    }

    int n;
    void solve() throws IOException {
        n = nextInt();
        int q = nextInt();
        arr = nextLongArr(n);
        sumTree = new long[5 * n];
        maxTree = new int[5 * n];
        build_tree(1, 0, n - 1);

        for (int p = 0; p < q; p++) {
            int pi = nextInt() - 1;
            long x = nextInt();

            long diff = x - arr[pi];
            arr[pi] = x;
            update_max_tree(1, 0, n - 1, pi, x);
            update_sum_tree(1, 0, n - 1, pi, diff);

            int start = -1;
            int res = -1;
            while (start < n - 1) {
                long sum = query_sum_tree(1, 0, n - 1, 0, start);
                int idx = query_max_tree(1, 0, n - 1, start + 1, n - 1, sum);
                long pref = query_sum_tree(1, 0, n - 1, 0, idx - 1);
                if (idx != n && arr[idx] == pref) {
                    res = idx;
                    break;
                }

                start = idx;
            }

            outln(res == -1 || res == n ? -1 : (1 + res));
        }
    }

    void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }

    long gcd(long a, long b) {
        while(a != 0 && b != 0) {
            long c = b;
            b = a % b;
            a = c;
        }
        return a + b;
    }

    private void outln(Object o) {
        out.println(o);
    }
    private void out(Object o) {
        out.print(o);
    }
    private void formatPrint(double val) {
        outln(String.format("%.9f%n", val));
    }
    public CFG() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
    public static void main(String[] args) throws IOException {
        new CFG();
    }

    public long[] nextLongArr(int n) throws IOException{
        long[] res = new long[n];
        for(int i = 0; i < n; i++)
            res[i] = nextLong();
        return res;
    }
    public int[] nextIntArr(int n) throws IOException {
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nextInt();
        return res;
    }
    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }
    public String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}