1556_E. Equilibrium_168
<image>

William has two arrays a and b, each consisting of n items.

For some segments l..r of these arrays William wants to know if it is possible to equalize the values of items in these segments using a balancing operation. Formally, the values are equalized if for each i from l to r holds a_i = b_i.

To perform a balancing operation an even number of indices must be selected, such that l ≤ pos_1 < pos_2 < ... < pos_k ≤ r. Next the items of array a at positions pos_1, pos_3, pos_5, ... get incremented by one and the items of array b at positions pos_2, pos_4, pos_6, ... get incremented by one.

William wants to find out if it is possible to equalize the values of elements in two arrays for each segment using some number of balancing operations, and what is the minimal number of operations required for that. Note that for each segment the operations are performed independently.

Input

The first line contains a two integers n and q (2 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5), the size of arrays a and b and the number of segments.

The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^9).

The third line contains n integers b_1, b_2, ..., b_n (0 ≤ b_i ≤ 10^9).

Each of the next q lines contains two integers l_i and r_i (1 ≤ l_i < r_i ≤ n), the edges of segments.

Output

For each segment output a single number — the minimal number of balancing operations needed or "-1" if it is impossible to equalize segments of arrays.

Example

Input


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


Output


1
3
1
-1
-1

Note

For the first segment from 2 to 6 you can do one operation with pos = [2, 3, 5, 6], after this operation the arrays will be: a = [0, 2, 2, 9, 4, 2, 7, 5], b = [2, 2, 2, 9, 4, 2, 5, 8]. Arrays are equal on a segment from 2 to 6 after this operation.

For the second segment from 1 to 7 you can do three following operations: 

  1. pos = [1, 3, 5, 6] 
  2. pos = [1, 7] 
  3. pos = [2, 7] 



After these operations, the arrays will be: a = [2, 2, 2, 9, 4, 2, 7, 5], b = [2, 2, 2, 9, 4, 2, 7, 8]. Arrays are equal on a segment from 1 to 7 after these operations.

For the third segment from 2 to 4 you can do one operation with pos = [2, 3], after the operation arrays will be: a = [0, 2, 2, 9, 3, 2, 7, 5], b = [2, 2, 2, 9, 4, 1, 5, 8]. Arrays are equal on a segment from 2 to 4 after this operation.

It is impossible to equalize the fourth and the fifth segment.
/*
stream Butter!
eggyHide eggyVengeance
I need U
xiao rerun when
 */
import static java.lang.Math.*;
import java.util.*;
import java.io.*;
import java.math.*;

public class x1556E
{
    public static void main(String hi[]) throws Exception
    {
        FastScanner infile = new FastScanner();
        int N = infile.nextInt();
        int Q = infile.nextInt();
        int[] arr = infile.nextInts(N);
        int[] brr = infile.nextInts(N);
        for(int i=0; i < N; i++)
            arr[i] -= brr[i];
        //increase 1, decrease 1, etc
        long[] psums = new long[N];
        psums[0] = arr[0];
        for(int i=1; i < N; i++)
            psums[i] = psums[i-1]+arr[i];
        LazySegTree segtree = new LazySegTree(N);
        LazySegTreeMin rmq = new LazySegTreeMin(N);
        for(int i=0; i < N; i++)
        {
            segtree.update(i, i, psums[i]);
            rmq.update(i, i, psums[i]);
        }
        ArrayList<Query> queries = new ArrayList<Query>();
        for(int i=0; i < Q; i++)
        {
            int left = infile.nextInt()-1;
            int right = infile.nextInt()-1;
            queries.add(new Query(left, right, i));
        }
        Collections.sort(queries);
        long[] res = new long[Q];
        int pointer = 0;
        for(Query q: queries)
        {
            int L = q.left;
            int R = q.right;
            while(pointer < L)
            {
                segtree.update(pointer, N-1, -1*arr[pointer]);
                rmq.update(pointer, N-1, -1*arr[pointer]);
                pointer++;
            }
            long tot = psums[R];
            if(L > 0)   tot -= psums[L-1];
            if(tot != 0)
                res[q.id] = -1;
            else
            {
                if(segtree.query(L, R) > 0)
                    res[q.id] = -1;
                else
                    res[q.id] = -1*rmq.query(L, R);
            }
        }
        StringBuilder sb = new StringBuilder();
        for(long x: res)
            sb.append(x+"\n");
        System.out.print(sb);
    }
}
class LazySegTree
{
    //definitions
    private long NULL = Long.MIN_VALUE/2;
    private long[] tree;
    private long[] lazy;
    private int length;

    public LazySegTree(int N)
    {
        length = N;   int b;
        for(b=0; (1<<b) < length; b++);
        tree = new long[1<<(b+1)];
        lazy = new long[1<<(b+1)];
    }
    public long query(int left, int right)
    {
        //left and right are 0-indexed
        return get(1, 0, length-1, left, right);
    }
    private long get(int v, int currL, int currR, int L, int R)
    {
        if(L > R)
            return NULL;
        if(L <= currL && currR <= R)
            return tree[v];
        propagate(v);
        int mid = (currL+currR)/2;
        return comb(get(v*2, currL, mid, L, Math.min(R, mid)),
                get(v*2+1, mid+1, currR, Math.max(L, mid+1), R));
    }
    public void update(int left, int right, long delta)
    {
        add(1, 0, length-1, left, right, delta);
    }
    private void add(int v, int currL, int currR, int L, int R, long delta)
    {
        if(L > R)
            return;
        if(currL == L && currR == R)
        {
            //exact covering
            tree[v] += delta;
            lazy[v] += delta;
            return;
        }
        propagate(v);
        int mid = (currL+currR)/2;
        add(v*2, currL, mid, L, Math.min(R, mid), delta);
        add(v*2+1, mid+1, currR, Math.max(L, mid+1), R, delta);
        tree[v] = comb(tree[v*2], tree[v*2+1]);
    }
    private void propagate(int v)
    {
        //tree[v] already has lazy[v]
        if(lazy[v] == 0)
            return;
        tree[v*2] += lazy[v];
        lazy[v*2] += lazy[v];
        tree[v*2+1] += lazy[v];
        lazy[v*2+1] += lazy[v];
        lazy[v] = 0;
    }
    private long comb(long a, long b)
    {
        return max(a,b);
    }
}
class LazySegTreeMin
{
    //definitions
    private long NULL = Long.MAX_VALUE/2;
    private long[] tree;
    private long[] lazy;
    private int length;

    public LazySegTreeMin(int N)
    {
        length = N;   int b;
        for(b=0; (1<<b) < length; b++);
        tree = new long[1<<(b+1)];
        lazy = new long[1<<(b+1)];
    }
    public long query(int left, int right)
    {
        //left and right are 0-indexed
        return get(1, 0, length-1, left, right);
    }
    private long get(int v, int currL, int currR, int L, int R)
    {
        if(L > R)
            return NULL;
        if(L <= currL && currR <= R)
            return tree[v];
        propagate(v);
        int mid = (currL+currR)/2;
        return comb(get(v*2, currL, mid, L, Math.min(R, mid)),
                get(v*2+1, mid+1, currR, Math.max(L, mid+1), R));
    }
    public void update(int left, int right, long delta)
    {
        add(1, 0, length-1, left, right, delta);
    }
    private void add(int v, int currL, int currR, int L, int R, long delta)
    {
        if(L > R)
            return;
        if(currL == L && currR == R)
        {
            //exact covering
            tree[v] += delta;
            lazy[v] += delta;
            return;
        }
        propagate(v);
        int mid = (currL+currR)/2;
        add(v*2, currL, mid, L, Math.min(R, mid), delta);
        add(v*2+1, mid+1, currR, Math.max(L, mid+1), R, delta);
        tree[v] = comb(tree[v*2], tree[v*2+1]);
    }
    private void propagate(int v)
    {
        //tree[v] already has lazy[v]
        if(lazy[v] == 0)
            return;
        tree[v*2] += lazy[v];
        lazy[v*2] += lazy[v];
        tree[v*2+1] += lazy[v];
        lazy[v*2+1] += lazy[v];
        lazy[v] = 0;
    }
    private long comb(long a, long b)
    {
        return min(a,b);
    }
}
class Query implements Comparable<Query>
{
    public int left;
    public int right;
    public int id;

    public Query(int a, int b, int i)
    {
        left = a;
        right = b;
        id = i;
    }
    public int compareTo(Query oth)
    {
        return left-oth.left;
    }
}
class FastScanner
{
    //I don't understand how this works lmao
    private int BS = 1 << 16;
    private char NC = (char) 0;
    private byte[] buf = new byte[BS];
    private int bId = 0, size = 0;
    private char c = NC;
    private double cnt = 1;
    private BufferedInputStream in;

    public FastScanner() {
        in = new BufferedInputStream(System.in, BS);
    }

    public FastScanner(String s) {
        try {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        } catch (Exception e) {
            in = new BufferedInputStream(System.in, BS);
        }
    }

    private char getChar() {
        while (bId == size) {
            try {
                size = in.read(buf);
            } catch (Exception e) {
                return NC;
            }
            if (size == -1) return NC;
            bId = 0;
        }
        return (char) buf[bId++];
    }

    public int nextInt() {
        return (int) nextLong();
    }

    public int[] nextInts(int N) {
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            res[i] = (int) nextLong();
        }
        return res;
    }

    public long[] nextLongs(int N) {
        long[] res = new long[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextLong();
        }
        return res;
    }

    public long nextLong() {
        cnt = 1;
        boolean neg = false;
        if (c == NC) c = getChar();
        for (; (c < '0' || c > '9'); c = getChar()) {
            if (c == '-') neg = true;
        }
        long res = 0;
        for (; c >= '0' && c <= '9'; c = getChar()) {
            res = (res << 3) + (res << 1) + c - '0';
            cnt *= 10;
        }
        return neg ? -res : res;
    }

    public double nextDouble() {
        double cur = nextLong();
        return c != '.' ? cur : cur + nextLong() / cnt;
    }

    public double[] nextDoubles(int N) {
        double[] res = new double[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextDouble();
        }
        return res;
    }

    public String next() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c > 32) {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public String nextLine() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c != '\n') {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public boolean hasNext() {
        if (c > 32) return true;
        while (true) {
            c = getChar();
            if (c == NC) return false;
            else if (c > 32) return true;
        }
    }
}