Maximum Intersection of Horizontal and Vertical Segments

We are given a plane with n vertical segments. The i-th vertical segment has endpoints \( (i, a_i) \) and \( (i, b_i) \). In other words, the segment spans from \( \min(a_i,b_i) \) to \( \max(a_i,b_i) \) along the y-axis at x-coordinate \( i \).

There are m queries. Each query provides four integers \( l, r, x, y \). For each query, consider all horizontal segments defined by the two endpoints \( (x, i) \) and \( (y, i) \) where \( i \) can be any integer in the interval \( [l, r] \). Let the horizontal segment span from \( \min(x,y) \) to \( \max(x,y) \) in the x-axis, with y-coordinate equal to \( i \).

A vertical segment with endpoints \( (j, a_1) \) and \( (j, a_2) \) and a horizontal segment with endpoints \( (b_1, i) \) and \( (b_2, i) \) are considered to intersect if and only if both conditions hold: \[ a_1 \le i \le a_2 \quad \text{and} \quad b_1 \le j \le b_2. \] Note that even if segments share an endpoint and another segment passes through that endpoint, it is still counted as an intersection.

For each query, you are to choose an integer \( i \) in \( [l, r] \) (which determines the horizontal segment \( (x,i)-(y,i) \)) so that the number of intersections with the vertical segments (with indices in \( [\min(x,y),\max(x,y)] \)) is maximized. Print the maximum intersection count for the optimal choice of \( i \).

inputFormat

The first line contains two integers n and m --- the number of vertical segments and the number of queries.

The second line contains n integers: \( a_1, a_2, \dots, a_n \).

The third line contains n integers: \( b_1, b_2, \dots, b_n \).

Then follow m lines, each containing four integers: l, r, x and y, which represent a query.

outputFormat

For each query, output a single line with the maximum number of intersections between the chosen horizontal segment and the vertical segments (only considering vertical segments with indices between \( \min(x,y) \) and \( \max(x,y) \)).

sample

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

5
3
1