У Nezzar есть бинарная строка \(s\) длины \(n\), которой он хочет поделиться со своим лучшим другом, Nanako. Он будет в течение \(q\) дней проверять эту бинарную строку. В то же время Nezzar хочет изменить свою строку \(s\) так, чтобы она через \(q\) дней стала равна более красивой строке \(f\).
Известно, что Nanako очень любит однообразие. В \(i\)-й день Nanako будет проверять отрезок строки \(s\) с позиции \(l_i\) по позицию \(r_i\) включительно. Если на этом отрезке есть символы и «0», и «1», Nanako очень расстроится и выкинет строку.
После каждой проверки, в \(i\)-ю ночь Nezzar может тайно поменять строго меньше, чем половину символов на отрезке с \(l_i\) по \(r_i\) включительно (потому что иначе изменение будет слишком очевидным).
Сейчас Nezzar интересуется, можно ли избежать того, что Nanako расстроится, и вместе с этим получить строку \(f\) в конце этих \(q\) дней и ночей.
Выходные данные
Для каждого набора входных данных в собственной строке выведите «YES», если можно избежать того, что Nanako расстроится, и получить строку \(f\) в конце \(q\) дней и ночей. Иначе выведите «NO».
Вы можете вывести каждый символ в любом регистре (верхнем или нижнем).
Примечание
В первом наборе входных данных \(\underline{00000} \rightarrow \underline{000}11 \rightarrow 00111\) — одна из возможных последовательностей изменений строки.
Во втором наборе входных данных можно показать, что невозможно получить строку \(f\) в конце.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 2
00000
00111
1 5
1 3
2 1
00
01
1 2
10 6
1111111111
0110001110
1 10
5 9
7 10
1 7
3 5
6 10
5 2
10000
11000
2 5
1 3
|
YES
NO
YES
NO
|