Всем известно, что самый вкусный фрукт на земле - это яблоки. Знает это даже обезьяна Крис. Яблоки растут в лесу, в котором есть много яблонь, расположенных вдоль реки и пронумерованных последовательно начиная с 1. Иногда Крис приходит в лес, проходит несколько стоящих подряд яблонь (выбранный им интервал) и считает количество яблонь со спелыми яблоками среди них. Кроме того, бывает так, что к его очередному приходу на нескольких рядом стоящих яблонях уже созрели яблоки.
Для каждого прихода Криса нужно сказать, сколько яблонь с созревшими яблоками находятся в выбранном им интервале. В начале все яблони не созревшие.
В первой строке дается целое число m (1 ≤ m ≤ 100000) - количество событий. Следующие m строк содержат описания событий - по три целых числа d[i]
, x[i]
, y[i]
(1 ≤ d[i]
≤ 2, x[i]
≤ y[i]
). Если первое число d[i]
= 1, то описываемое событие - это приход Криса, а если d[i]
= 2 - созревание яблок на яблонях. Остальные два числа x[i]
и y[i]
, описывают интервал для события.
В вычислении границ интервала также участвует число с, изначально равное 0. Интервал для события - это интервал от x[i]
+ c до y[i]
+ c включительно. Гарантируется, что 1 ≤ x[i]
+ c, y[i]
+ c ≤ 10^9
. Если событие - это созревание яблок, то значение c не меняется, а если приход Криса, то в подсчете границ интервала участвует предыдущее значение c, а в результате c становится равным количеству яблонь с созревшими яблоками в указанном интервале.
Для каждого прихода Криса выведите одну строку, содержащую одно число, - ответ к задаче.