Island Adventure: Counting Happy Explorations

Frost is an adventurous girl who loves to explore. One day, she visits a sea area that contains \( n \) islands arranged in a line and numbered \(1, 2, \ldots, n\). Each island has two attributes: fatigue value \( a_i \) and fun value \( b_i \).

For an island with fatigue \( a \) and fun \( b \), if it satisfies the condition

[ (a \oplus c) \leq \min(b, d), ]

where \( c \) and \( d \) represent Frost's initial fatigue and fun levels respectively, and \( \oplus \) denotes the bitwise XOR, then exploring that island makes her happy.

Frost will ask you \( q \) queries. In each query, you are given a segment \( [l, r] \) (the indices of islands to consider) and two integers \( c \) and \( d \) denoting her initial fatigue and fun levels. Your task is to determine how many islands in the segment \( [l, r] \) will make her happy.

inputFormat

The first line contains two integers \( n \) and \( q \) --- the number of islands and the number of queries.

The second line contains \( n \) integers \( a_1, a_2, \ldots, a_n \) representing the fatigue values of the islands.

The third line contains \( n \) integers \( b_1, b_2, \ldots, b_n \) representing the fun values of the islands.

Then \( q \) lines follow. Each of these lines contains four integers \( l, r, c, d \):

• \( l \) and \( r \) define the segment of islands to consider (1-indexed).
• \( c \) is the initial fatigue.
• \( d \) is the initial fun value.

outputFormat

For each query, output a single integer representing the number of islands in the segment \( [l, r] \) that satisfy the condition \((a \oplus c) \leq \min(b, d)\).

Each answer should be printed on a new line.

sample

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

3
2
0