Olympiad in Informatics

Mã khóa bí mật

Hè đã về! Ktuan đã tự hứa sẽ làm một việc gì đó có ích trong hè này, và bây giờ là lúc ktuan bắt đầu.

Ktuan đi thuyền tới một hòn đảo giấu vàng. Sau nhiều ngày tìm kiếm, ktuan phát hiện ra một chiếc hòm đã bị khóa. Hiển nhiên ktuan không thể phá khóa vì hệ thống kích nổ sẽ hoạt động, và cái ktuan nhận được sẽ chỉ là một đống tro. Do đó việc tìm chìa khóa để mở chiếc hòm là rất cần thiết.

Chìa khóa này là một dãy số nhị phân (tức là dãy số chỉ gồm số 0 và 1) có độ dài n. Các chữ số được đánh số thứ tự 1 đến n từ trái sang phải. Ktuan đã thu thập được một số chữ số của dãy số. Ngoài ra, ktuan còn thu thập được thêm một số thông tin từ những người đến trước (nhưng thất bại trong việc mở khóa). Mỗi thông tin có dạng: "Tồn tại k chữ số x liên tiếp từ vị trí a đến vị trí b".

Ví dụ, nếu ktuan đã biết dãy số có 5 chữ số có dạng 1???? với ? là chữ số chưa biết, và biết thêm "tồn tại 3 chữ số 0 liên tiếp từ vị trí 2 đến vị trí 5", thì dãy số có thể là 10001, 10000 hoặc 11000. Do đó ktuan có thể chắc chắn rằng chữ số thứ 3 và thứ 4 là 0. Như vậy dãy số có dạng 1?00?.

Cho dạng của dãy số và các thông tin, giúp ktuan xác định các chữ số còn lại của mã khóa.

Dữ liệu

• Dòng đầu ghi 2 số n, m là số lượng chữ số của dãy và số lượng thông tin đã biết (1 ≤ n ≤ 50, 1 ≤ m ≤ 25).
• Dòng sau ghi n ký tự là '0', '1' hoặc '?' tương ứng là chữ số 0, chữ số 1 hoặc chữ số đó chưa rõ.
• m dòng sau, mỗi dòng ghi 4 số k, x, a, b tương ứng với 1 câu thông tin.

Kết quả

• Ghi 1 dòng n ký tự thể hiện mã khóa, những ký tự không thể xác định được thay bằng '?'.
• Nếu các thông tin mâu thuẫn, ghi ra "mau thuan" (và điều này sẽ thực sự là một cơn ác mộng đối với ktuan).

Hạn chế

Có 30% số test, tương ứng với 30% số điểm, trong đó 1 ≤ n ≤ 20 và 1 ≤ m ≤ 20

Ví dụ

Dữ liệu
5 1
1????
3 0 2 5

Kết quả
1?00?