Cafe 12

There is a restaurant named Cafe 12. They have arranged their seats in two rows, each row consists of $N$ seats. In this cafe people can come alone (single) or with his/her partner (couples). When a couple comes into this cafe they must sit in two adjacent empty seats either in the same rows or in the same column. Single people can sit in any empty seats he would like to prefer.

You are given the current situation of the cafe. The empty seats will be represented by $0$ and the booked seats will be represented by $1$. You have to answer $Q$ queries. In each query you are given two integers $x$ and $y$, the number of couples and the number of single people respectively. You have to find whether it is possible to arrange seats for $x$ couples and $y$ single people without violating the rules given. Each query is independent.

Input

The first line contains two integers $N (1 \leq N \leq 10^6)$ and $Q (1 \leq Q \leq 10^6)$, the number of seats in each row and the number of queries.

The next two lines represent the current situation of the cafe where the empty seats will be represented by $0$ and the booked seats will be represented by $1$.

The next $Q$ lines contain two integers $x$ and $y$, the number of couples and the number of single people respectively.

Output

For each query, print $\texttt{“YES”}$ (without quotes) if it is possible to arrange seats without violating the rules, or $\texttt{“NO”}$ (without quotes) otherwise (case insensitive, for example, "Yes", "yes", "YES", etc are equivalent.) on a separate line.

Sample

Input	Output
6 3 000000 010010 3 4 4 3 4 2	YES NO YES