Problem Description

The school where Little Z lives is like a chain: very long in diameter and very narrow in width.

More specifically, there is a sequence of length $n$. Each position has an attribute $a_i\in \{0/1\}$ and a type $c_i$. Some trading events will happen here.

Little Z moves through the sequence from left to right. If Little Z encounters a node with attribute $0$, then Little Z may buy at most one item of type $c_i$. If Little Z encounters a node with attribute $1$, then Little Z may sell at most one item of type $c_i$. Obviously, Little Z cannot sell an item of a type that Little Z does not have.

A legal transaction is defined as buying at some node and selling at some node. Note that you must ensure that, in the end, Little Z has nothing left in hand.

There are $q$ queries. In each query, Little Z walks in order from $l_i$ to $r_i$. Ask: what is the maximum number of legal transactions?

Input Format

The first line contains two positive integers $n,q$.

The next line contains $n$ numbers, where the $i$-th one denotes $a_i$.

The next line contains $n$ numbers, where the $i$-th one denotes $c_i$.

The next $q$ lines each contain two numbers denoting $l_i,r_i$.

Output Format

Output $q$ lines in total, each line containing one number denoting the maximum number of legal transactions in the current query.

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 7

0
0
0
1
0

Hint

For all testdata, it holds that $1\le n,q\le5\times 10^5,1\le c_i\le n,1\le l_i\le r_i\le n,a_i\in\{0,1\}$.

Please pay attention to input/output efficiency.

Source and Acknowledgements

From the finals of THUPC2024 (Tsinghua University Student Programming Contest 2024 and Collegiate Invitational). Thanks to THUSAA for providing the problem.

For data, statement, reference solution, editorial, etc., please refer to the official THUPC repository https://thusaac.com/public.

Translated by ChatGPT 5