Герои Могущие Магию идут по прямой дороге и сражаются с бесами. Бесы слабые и уязвимые существа, и не являются интересными соперниками, но нашим героям нравится с ними сражаться. Потому что это весело.

Герой Игнатиус просто обожает бесов. Перед ним находится прямая с бесами, которая может быть представлена как массив целых чисел a длины n (в индексации с 0), где a_i означает количество бесов в позиции i. Иногда из ниоткуда появляются новые бесы. Когда герой собирается сражаться с бесами, он выбирает некоторый отрезок данной прямой, начинает в одном конце отрезка и заканчивает в другом, ни в какой момент не покидая отрезок. Герой может перемещаться на одну позицию влево или на одну позицию вправо. Каждый раз, когда герой выполняет перемещение, он убивает одного беса в клетке, куда он пришёл, то есть количество бесов в этой клетке уменьшается на 1. Также герой убивает одного беса когда только появляется в крайней клетке отрезка в начале маршрута.

Целью героев является победить всех бесов на отрезке и при этом никогда не делать ход в пустую клетку (где нет бесов), потому что это скучно. Игнатиус любит бесов, поэтому он на самом деле их не убивает, так что при подготовке этой задачи ни один бес не пострадал. Однако, он бы хотел, чтобы вы отвечали ему на вопросы, возможно ли зачистить от бесов некоторый отрезок, если действовать согласно правилам выше.

Требуется обработать q различных запросов:

• 1 a b k — k бесов появляются в каждой клетке отрезка [a, b].
• 2 a b — Игнатиус хочет знать, можно ли победить всех бесов на отрезке [a, b], действую согласно описанным выше правилам.