МУУУУУУУУУУУУУУУУУ
— Корова Бесси, Искусство гонок по островам
Две коровы фермера Джона, Бесси и Элси, планируют участвовать в гонках по \(n\) островам. Существует \(n - 1\) основных мостов, соединяющих остров \(i\) с островом \(i + 1\) для всех \(1 \leq i \leq n - 1\). Кроме того, существует \(m\) альтернативных мостов. Элси может использовать и основные, и альтернативные мосты, а Бесси — только основные. Все мосты являются односторонними и могут использоваться только для перемещения с острова с меньшим индексом на остров с большим индексом.
Изначально Элси находится на острове \(1\), а Бесси — на острове \(s\). Коровы ходят по очереди, причем Бесси ходит первой. Предположим, что корова находится на острове \(i\). Во время хода коровы, если есть мост, соединяющий остров \(i\) с островом \(j\), то корова может переместиться на остров \(j\). Затем остров \(i\) разрушается, и все мосты, соединяющие остров \(i\), также разрушаются. Обратите внимание на следующее:
- Если нет мостов, соединяющих остров \(i\) с другим островом, то остров \(i\) разрушается, и эта корова выбывает из гонки.
- Если другая корова также находится на острове \(i\), то после того, как эта корова переместится на другой остров, остров разрушится, и другая корова выбывает из гонки.
- После того, как остров или мост разрушились, ни одна корова не может ими воспользоваться.
- Если корова выбывает из гонки, ее ход пропускается до конца гонки.
Гонка заканчивается, как только одна из коров достигнет острова \(n\). Можно показать, что независимо от стратегий коров, хотя бы одна из них достигнет острова \(n\). Бесси побеждает тогда и только тогда, когда она первой достигает острова \(n\).
Для каждого \(1 \leq s \leq n - 1\) определите, выиграет ли Бесси, если она начнет гонку на острове \(s\). Предположим, что обе коровы следуют оптимальным стратегиям, чтобы обеспечить себе победу.
Выходные данные
Для каждого набора входных данных выведите в отдельной строке бинарную строку длины \(n - 1\). \(i\)-й символ равен \(1\), если Бесси может выиграть, если она начнет с острова \(i\). В противном случае он равен \(0\).
Примечание
В первом наборе входных данных нет альтернативных мостов, по которым Элси могла бы обогнать Бесси и первой достичь острова \(n\), поэтому Бесси выиграет на всех островах, потому что она всегда ходит первой.
Во втором случае Бесси проиграет, если начнет с острова \(3\), потому что:
- Ход Бесси: Перейти по основному мосту с острова \(3\) на остров \(4\).
- Ход Элси: Перейти по основному мосту с острова \(1\) на остров \(2\).
- Ход Бесси: Перейти по основному мосту с острова \(4\) на остров \(5\).
- Ход Элси: Перейти по альтернативному мосту с острова \(2\) на остров \(6\). Элси первой достигает острова \(n\).