Codeforces Round 974 (Div. 3) |
---|
Finished |
Sheriff of Nottingham has organized a tournament in archery. It's the final round and Robin Hood is playing against Sheriff!
There are $$$n$$$ targets in a row numbered from $$$1$$$ to $$$n$$$. When a player shoots target $$$i$$$, their score increases by $$$a_i$$$ and the target $$$i$$$ is destroyed. The game consists of turns and players alternate between whose turn it is. Robin Hood always starts the game, then Sheriff and so on. The game continues until all targets are destroyed. Both players start with score $$$0$$$.
At the end of the game, the player with most score wins and the other player loses. If both players have the same score, it's a tie and no one wins or loses. In each turn, the player can shoot any target that wasn't shot before. Both play optimally to get the most score possible.
Sheriff of Nottingham has a suspicion that he might lose the game! This cannot happen, you must help Sheriff. Sheriff will pose $$$q$$$ queries, each specifying $$$l$$$ and $$$r$$$. This means that the game would be played only with targets $$$l, l+1, \dots, r$$$, as others would be removed by Sheriff before the game starts.
For each query $$$l$$$, $$$r$$$, determine whether the Sheriff can not lose the game when only considering the targets $$$l, l+1, \dots, r$$$.
The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains two integers $$$n$$$, $$$q$$$ ($$$1 \le n,q \le 2\cdot10^5$$$) — the number of targets and the queries Sheriff will pose.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the points for hitting each target.
Then follow $$$q$$$ lines, each with two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the range of the targets that is considered for each query.
It is guaranteed that the sum of both $$$n$$$ and $$$q$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.
For each query, output "YES", if the Sheriff does not lose the game when only considering the targets $$$l, l+1, \dots, r$$$, and "NO" otherwise.
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
23 31 2 21 21 32 35 32 1 2 1 11 21 34 5
NO NO YES NO NO YES
Name |
---|