Однажды, когда Рудольф возвращался пешком домой из лаборатории, на улице внезапно начался дождь. К сожалению, зонт с собой Рудольф не взял. Но, с другой стороны, Рудольф — настоящий программист, а это значит, что ему известны некоторые тайны окружающего мира.

Рудольф точно знает, что наша вселенная — не что иное как гигантская компьютерная симуляция. Конечно же, Рудольф умеет её взламывать: например, лёгким взмахом руки он может остановить капли дождя над головой, прямо как Нео из Матрицы останавливал летящие пули.

Поэтому Рудольф может пройти под дождём, совершенно не промокнув. Или же нет?..

Рудольф немного располнел за зиму, поэтому его профиль представляет собой квадрат N × N, левый нижний угол которого в момент времени 0 расположен в точке (0;0). Рудольф непрерывно движется вправо, проходя 1 единицу расстояния за 1 секунду.

Дождь состоит из M отдельных капель, падающих вертикально вниз с постоянной скоростью. i-я капля в момент времени 0 находится в позиции (X_i;Y_i), а за 1 секунду преодолевает V_i единиц расстояния. Капля попадает в Рудольфа, если существует такой момент времени (целый или дробный), когда капля находится в воздухе (Y_i > 0) и пересекается с профилем Рудольфа.

Чтобы останавливать капли дождя, Рудольф K раз поднимает руку; время выполнения j-го жеста — [L_j, R_j). Пока рука Рудольфа поднята, все капли, находящиеся над ним (то есть между левой и правой границами и выше верхней границы его профиля), меняют характер своего движения. Если капля находится на высоте не более 2N, то она вообще не двигается; если капля находится на высоте более 2N, то она продолжает падать вниз, но останавливается, если достигнет высоты 2N.

Попробуйте определить, промокнет ли Рудольф под дождём.