The school where Xiao Z lives is like a chain: very long in diameter and very narrow in width.
Specifically, there is a sequence of length $n$, where each position has an attribute $a_i \in \{0, 1\}$ and a type $c_i$. Various trade events occur here.
Xiao Z moves through this sequence from left to right. If they encounter a node with attribute $0$, Xiao Z can purchase at most one item of type $c_i$. If they encounter a node with attribute $1$, Xiao Z can sell at most one item of type $c_i$. Obviously, they cannot sell an item of a certain type if they do not currently possess one.
A valid trade is defined as buying an item at some node and selling it at some later node. Note that you must ensure Xiao Z does not hold any items at the end.
Given $q$ queries, each asking for the maximum number of valid trades Xiao Z can make while walking from $l_i$ to $r_i$ in order.
For each query, given an interval, enumerate the elements in the interval in order. When encountering an attribute $0$, purchase an item of that color; when encountering an attribute $1$, sell an item of that color. The value is defined as the number of successful sales (a sale is successful if the current number of items of that color purchased minus the number sold is $\ge 1$).
Input
Read data from standard input.
The first line contains two positive integers $n$ and $q$.
The next line contains $n$ integers, where the $i$-th integer represents $a_i$.
The next line contains $n$ integers, where the $i$-th integer represents $c_i$.
The next $q$ lines each contain two integers representing $l_i$ and $r_i$.
Output
Output to standard output.
Output $q$ lines, each containing a single integer representing the maximum number of valid trades for the current query.
Examples
Input 1
10 5
1 1 0 0 0 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1
4 6
2 4
2 6
7 10
4 7Output 1
0
0
0
1
0Subtasks
For all data, $1 \le n, q \le 5 \times 10^5$, $1 \le c_i \le n$, $1 \le l_i \le r_i \le n$, and $a_i \in \{0, 1\}$.
Note
Please pay attention to input and output efficiency.