Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Cafe 12

By Pranta07 · Limits 1s, 256 MB

There is a restaurant named Cafe 12. They have arranged their seats in two rows, each row consists of NN 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 00 and the booked seats will be represented by 11. You have to answer QQ queries. In each query you are given two integers xx and yy, the number of couples and the number of single people respectively. You have to find whether it is possible to arrange seats for xx couples and yy single people without violating the rules given. Each query is independent.

Input

The first line contains two integers N(1N106)N (1 \leq N \leq 10^6) and Q(1Q106)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 00 and the booked seats will be represented by 11.

The next QQ lines contain two integers xx and yy, the number of couples and the number of single people respectively.

Output

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

Sample

InputOutput
6 3
000000
010010
3 4
4 3
4 2
YES
NO
YES

    Discussion

    Statistics


    51% Solution Ratio

    ashraf_pavelEarliest, 4M ago

    JobaidulFastest, 0.1s

    tareq_sakibLightest, 5.9 MB

    Zobayer_AbedinShortest, 788B

    Submit

    Login to submit

    Editorial

    Prerequisites: Greedy/ Dynamic Programming Explanation: First, lets have an easy observation that it...

    Toph uses cookies. By continuing you agree to our Cookie Policy.