There is a restaurant named Cafe 12. They have arranged their seats in two rows, each row consists of 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 and the booked seats will be represented by . You have to answer queries. In each query you are given two integers and , the number of couples and the number of single people respectively. You have to find whether it is possible to arrange seats for couples and single people without violating the rules given. Each query is independent.
The first line contains two integers and , 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 and the booked seats will be represented by .
The next lines contain two integers and , the number of couples and the number of single people respectively.
For each query, print (without quotes) if it is possible to arrange seats without violating the rules, or (without quotes) otherwise (case insensitive, for example, "Yes", "yes", "YES", etc are equivalent.) on a separate line.
6 3 000000 010010 3 4 4 3 4 2
YES NO YES
Login to submit
Prerequisites: Greedy/ Dynamic Programming Explanation: First, lets have an easy observation that it...