Маленькому Леше улыбнулась удача: ему удалось раздобыть очень редкий и необычный массив A, состоящий из n целых чисел. Заполучив в свои руки такой ценный предмет, мальчик сразу же отнес его в свою подземную лабораторию, намереваясь постичь тайны устройства массива. Как опытный исследователь, Леша решил не спешить с проведением жутких экспериментов над бедным массивом, а сперва понаблюдать за ним. Он записал на листик бумаги результаты m наблюдений за массивом. Каждое наблюдение описывается тремя числами l_i, r_i и s_i, которые означают, что сумма элементов по модулю 2 на подотрезке [l_i, r_i] массива равна s_i. Леша подготовил все необходимое для проведения m + 1-го наблюдения, но тут он услышал, что мама зовет его обедать. По возвращении в свою лабораторию, мальчик увидел страшное: массив исчез. Совсем. Все надежды мальчика на получение Нобелевской премии в области исследования массивов рассыпались на глазах. Но потом Леша вспомнил, что у него все же осталась некоторая информация о массиве. Основываясь на записанных фактах, он решил построить компьютерную модель массива и проводить эксперименты над ней. Конечно, мальчик понимал, что он не сможет однозначно восстановить утерянный массив, потому что существует бесконечно много массивов, удовлетворяющих записанным фактам. Все мы знаем, что операции с большими числами занимают много времени, а если еще к тому же числа становятся отрицательными... Чтобы сделать свою компьютерную модель как можно более быстрой, Леша решил построить массив, удовлетворяющий известным фактам, элементы которого неотрицательны, а их сумма минимально возможная. Помогите ему сделать это!