Вы владеете полем, который можно представить как бесконечную числовую прямую, все позиции на которой отмечены целыми числами.
В следующие \(n\) дней будет идти дождь. В \(i\)-й день центр дождя будет располагаться в точке \(x_i\), а интенсивность дождя будет равна \(p_i\). Из-за дождей будет собираться дождевая вода; пусть \(a_j\) будет обозначать объем воды, накопившийся в точке \(j\). Изначально \(a_j\) равно \(0\), после дождя в \(i\)-й день это значение увеличится на \(\max(0,p_i-|x_i-j|)\).
Поле затопит, если в некоторый момент будет существовать точка \(j\), в которой накопится \(a_j>m\) воды.
Вы можете использовать заклинание и отменить дождь в ровно один из дней, т. е. установить \(p_i=0\). Для каждого \(i\) от \(1\) до \(n\) определите, если вы отмените дождь в \(i\)-й день, верно ли, что затопления не случится?
Выходные данные
Для каждого набора входных данных выведите бинарную строку \(s\) длины \(n\). \(i\)-й символ строки \(s\) должен быть равен 1, если в случае отмены дождя в \(i\)-й день затопления не случится, и 0, если в случае отмены дождя в \(i\)-й день затопление произойдет.
Примечание
В первом наборе входных данных, если не использовать заклинание, собравшаяся вода будет выглядеть следующим образом:
Если отменить дождь в третий день, затопление будет предотвращено, и собравшаяся вода будет выглядеть следующим образом:
Во втором примере изначально нет затопления, поэтому можно отменить дождь в любой день.
В третьем примере нет способа избежать затопления.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 6
1 5
5 5
3 4
2 3
1 3
5 2
2 5
1 6
10 6
6 12
4 5
1 6
12 5
5 5
9 7
8 3
|
001
11
00
100110
|