405682: GYM102035 F Who has a better strategy ?

Da'san and Abu Tahun are playing a video game, in that video game there are n monsters, the strength of the i_th monster is s_i, (1 ≤ s_i ≤ n), where each monster has a unique strength.

They both can defeat all monsters, Da'san needs a_i seconds to defeat the i_th monster and Abu Tahun needs b_i seconds to defeat the i_th monster.

Now they will play together at the same time, Abu Tahun will start killing monsters from the strongest one and Da'san will start killing monsters from the weakest one. The one who reaches a specific monster first will be the one to kill that monster. But if they came to kill the same monster at the same time, Abu Tahun will leave that monster to Da'san.

Now you are given q queries, for each query you are given a subarray from l to r, you should print the number of monsters each one of them will kill, if they both started playing the game with the monsters in the subarray from l to r.

The first line contains 2 integers n and q (1 ≤ n, q ≤ 2 × 10⁵) which are the number of monsters and the number of queries.

The second line will contain n distinct integers, the i_th one is s_i (1 ≤ s_i ≤ n) which is the strength of the i_th monster.

The Third line will contain n integers, the i_th one is a_i (1 ≤ a_i ≤ 10⁹), which is the time needed to kill the i_th monster by Da'san.

The Fourth line will contain n integers, the i_th one is b_i (1 ≤ b_i ≤ 10⁹), which is the time needed to kill the i_th monster by Abu Tahun.

The next q lines will contain 2 integers for each line, l and r (1 ≤ l ≤ r ≤ n), which is the sub-array that was given for the current query.

For each query print 2 integers, the number of monsters killed by Da'san and the number of monsters killed by Abu Tahun.

3 3
1 3 2
1 1 2
1 1 1
1 3
2 3
1 2

2 1
1 1
1 1

In the sample, for the first query at minute 0, Da'san will start with monster at index 1, and Abu Tahun will start with monster at index 2,

at minute 1 they will both go to kill the monster at index 3, and since they both came to kill the same monster at the same time Abu Tahun will leave that monster to Da'san.

So Da'san will kill 2 monsters and Abu Tahun will kill 1 monster.