Giải bài trực tuyến

The summer has come! Ktuan promised himself to do something new in this summer, and now it’s the time for him to start.

Ktuan goes sailing to a treasure island. After days searching, ktuan discovers a locked box. Obviously ktuan cannot break the lock because it will activate the mine to explode. Thus it is neccessary to find the key to open the box.

The key is a binary string of length n (that is a string consisting only of 0 and 1). The digits are numbered as 1 to n from left to right. Ktuan has collected some digits of the key successfully. Besides, ktuan has also collected some information about the key from the previous explorers (who fails to find the key). The information are statements of the form: “There are k consecutive digit x(s) from position a to position b (inclusive)”.

For example, if ktuan has known the key has 5 digits of the form 1???? (in which ? stands for an unknown digit), and he has also known that “there are 3 consecutive digit 0s from position 2 to position 5 (inclusive)", then the key can be 10001, 10000, or 11000. Ktuan is therefore sure that the third and the fourth digit is 0 and the key has the form 1?00?.

Given the form of the key and the information, help ktuan to determine the remaining digits of the key.

Input

• The first line contains two integers n and m that is the number of digits in the key and the number of statements of information (1 ≤ n ≤ 50, 1 ≤ m ≤ 25).
• The second line contains n characters ‘0’, ‘1’ or ‘?’ representing a 0, 1, or unknown digit in the key.
• Each line in the next m lines contains 4 integers k, x, a, b corresponding to one statement of information.

Output

• Print out a line representing the key in which the unknown digits are denoted by ?.
• If the statements are contradicted, print out ‘mau thuan’ (meaning ‘contradiction’ in Vietnamese).

Constraint

There are 30% of the test cases corresponding to 30% of the grades in which 1 ≤ n ≤ 20 and 1 ≤ m ≤ 20

Example

Input
5 1
1????
3 0 2 5

Output
1?00?