Da'san and Abu Tahun are playing a video game, in that video game there are n monsters, the strength of the ith monster is si, (1 ≤ si ≤ n), where each monster has a *unique* strength.
They both can defeat all monsters, Da'san needs ai seconds to defeat the ith monster and Abu Tahun needs bi seconds to defeat the ith 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 × 105) which are the number of monsters and the number of queries.
The second line will contain n distinct integers, the ith one is si (1 ≤ si ≤ n) which is the strength of the ith monster.
The Third line will contain n integers, the ith one is ai (1 ≤ ai ≤ 109), which is the time needed to kill the ith monster by Da'san.
The Fourth line will contain n integers, the ith one is bi (1 ≤ bi ≤ 109), which is the time needed to kill the ith 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.
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.
## Input
The first line contains 2 integers n and q (1 ≤ n, q ≤ 2 × 105) which are the number of monsters and the number of queries.The second line will contain n distinct integers, the ith one is si (1 ≤ si ≤ n) which is the strength of the ith monster.The Third line will contain n integers, the ith one is ai (1 ≤ ai ≤ 109), which is the time needed to kill the ith monster by Da'san.The Fourth line will contain n integers, the ith one is bi (1 ≤ bi ≤ 109), which is the time needed to kill the ith 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.
## Output
For each query print 2 integers, the number of monsters killed by Da'san and the number of monsters killed by Abu Tahun.
[samples]
## Note
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.
**Definitions**
Let $ n, q \in \mathbb{Z}^+ $ be the number of monsters and queries.
Let $ S = (s_1, s_2, \dots, s_n) $ be the sequence of distinct monster strengths, where $ s_i \in \{1, 2, \dots, n\} $.
Let $ A = (a_1, a_2, \dots, a_n) $ be the time required for Da'san to kill monster $ i $.
Let $ B = (b_1, b_2, \dots, b_n) $ be the time required for Abu Tahun to kill monster $ i $.
Let $ P $ be the permutation of indices $ \{1, 2, \dots, n\} $ such that $ s_{P(1)} < s_{P(2)} < \dots < s_{P(n)} $ (ascending order of strength).
Let $ Q $ be the permutation of indices $ \{1, 2, \dots, n\} $ such that $ s_{Q(1)} > s_{Q(2)} > \dots > s_{Q(n)} $ (descending order of strength).
For a query $ [l, r] $, define the subsequence of monsters by their original indices in $ [l, r] $.
Let $ M_{l,r} \subseteq \{l, l+1, \dots, r\} $ be the set of monster indices in the subarray.
Order $ M_{l,r} $ by increasing strength: $ m_1, m_2, \dots, m_k $ where $ k = r - l + 1 $, and $ s_{m_1} < s_{m_2} < \dots < s_{m_k} $.
**Constraints**
1. $ 1 \leq n, q \leq 2 \times 10^5 $
2. $ 1 \leq s_i \leq n $, all $ s_i $ distinct
3. $ 1 \leq a_i, b_i \leq 10^9 $
4. $ 1 \leq l \leq r \leq n $ for each query
**Objective**
For each query $ [l, r] $:
- Da'san starts at the weakest monster in $ M_{l,r} $ (i.e., $ m_1 $) and moves toward the strongest ($ m_k $), spending $ a_{m_j} $ seconds to kill monster $ m_j $.
- Abu Tahun starts at the strongest monster in $ M_{l,r} $ (i.e., $ m_k $) and moves toward the weakest ($ m_1 $), spending $ b_{m_j} $ seconds to kill monster $ m_j $.
- Time is synchronized: at time $ t $, Da'san has reached monster $ m_i $ if $ \sum_{j=1}^{i} a_{m_j} \leq t $, and Abu Tahun has reached monster $ m_i $ if $ \sum_{j=i}^{k} b_{m_j} \leq t $.
- Monster $ m_i $ is killed by:
- Da'san if $ \sum_{j=1}^{i} a_{m_j} < \sum_{j=i}^{k} b_{m_j} $,
- Abu Tahun if $ \sum_{j=1}^{i} a_{m_j} > \sum_{j=i}^{k} b_{m_j} $,
- Da'san if $ \sum_{j=1}^{i} a_{m_j} = \sum_{j=i}^{k} b_{m_j} $ (tie-breaker rule).
Compute $ d_{l,r} $ = number of monsters killed by Da'san,
and $ u_{l,r} $ = number of monsters killed by Abu Tahun in $ M_{l,r} $.
Output $ (d_{l,r}, u_{l,r}) $ for each query.