Chain Trading

There is a chain-like school represented as a sequence of length \( n \). Each position \( i \) in the sequence is characterized by an attribute \( a_i \) and a type \( c_i \). The attribute \( a_i \) is either 0 or 1. A trading event can occur at a node as follows:

• If \( a_i = 0 \) (buy node), Xiao Z can choose to buy at most one item of type \( c_i \).
• If \( a_i = 1 \) (sell node), he can sell at most one item of type \( c_i \), provided he currently holds at least one item of that type.

A valid transaction consists of buying an item at some buy node and later selling that same item at a sell node. In addition, the plan must ensure that by the time he reaches the end of his journey, Xiao Z does not hold any items (i.e. every purchased item must be sold).

You are given \( q \) queries. For each query, Xiao Z will traverse the sequence from index \( l_i \) to \( r_i \) (inclusive) in order. Determine the maximum number of valid transactions he can perform over that segment.

Note: A transaction for a specific type \( x \) is only possible if there is a buy (\( 0 \)) node with type \( x \) that appears before a sell (\( 1 \)) node with type \( x \) in the given interval. The maximum number is obtained by optimally choosing at which buy nodes to purchase so that all purchases can eventually be paired with a later sale of the same type.

inputFormat

The first line contains two integers \( n \) and \( q \) \( (1 \leq n, q \leq 10^5) \), representing the length of the sequence and the number of queries.

The second line contains \( n \) integers \( a_1, a_2, \dots, a_n \) where each \( a_i \in \{0,1\} \) indicates the attribute of the \( i^{th} \) node.

The third line contains \( n \) integers \( c_1, c_2, \dots, c_n \) indicating the type at each node.

Each of the next \( q \) lines contains two integers \( l_i \) and \( r_i \) \( (1 \leq l_i \leq r_i \leq n) \) representing a query.

outputFormat

For each query, output a single integer which is the maximum number of valid transactions that can be completed when traversing from \( l_i \) to \( r_i \).

sample

5 2
0 1 0 1 1
1 1 1 1 1
1 5
3 5

2
1