For the first subtask, it suffices to use two pointers for each query, which gives ~\mathcal{O}(N)~ per query.

Time Complexity: ~\mathcal{O}(QN)~

For the second subtask, we must make the following observation: suppose we have some subarray with sum ~S~. Observe that we can always remove some elements from the two ends of this subarray to obtain another subarray with sum ~S-2~. If either endpoint is a ~2~, we simply remove it and we are done. Otherwise, none of the two endpoints is a ~2~ which means they are both ~1~, so we remove both and we are done.

Therefore, if we have a subarray with sum ~S~, we can form any subarray with sum ~S'~ if ~S' \le S~ and ~S'~ has the same parity as ~S~. This means that we only care about the maximum subarray sum for each parity. This means each query is simplified down to checking for the maximum subarray sum of any subarray contained within ~l~ to ~r~ with the same parity as ~x~. For each index ~i~, we store the maximum prefix sum of any index before ~i~ and likewise we store the minimum prefix sum of any index after ~i~. Then each query can be done in ~\mathcal{O}(1)~ by simply subtracting the corresponding values to obtain the maximum subarray sum, ~X~, with the same parity as ~x~. If we can find a subarray with sum ~X \ge x~, the answer is YES, otherwise, the answer is NO.

Time Complexity: ~\mathcal{O}(N+Q)~