레몬 박물관

양의 정수 $k$가 주어지면, $k$개의 조명이 각각 $x$--축 위의 점들 $(2,0), ,(4,0), \cdots, (2k,0)$에 설치된다. 조명은 위 방향 좌우 $45^{\circ}$방향만 밝게 비춘다. 즉, 점 $(x, y)$가 조명 $i$에 의해 비춰지려면 $y \geq |x - 2i|$이어야 한다.

레몬은 정수 격자점 $(x, y)$ (단, $y \geq 2$)에만 달 수 있다. 한 점에 여러 개의 레몬을 달 수 있다.

음이 아닌 정수 $A_1, A_2, \cdots, A_k$에 대하여, $i$번 조명이 정확히 $A_i$개의 레몬을 비추도록 하려고 한다. 이것이 가능하다면 $f(A_1, A_2, \dots, A_k)$는 필요한 레몬의 최소 개수, 불가능하다면 $-1$로 정의한다.

예를 들어, $k = 4$이고 $(A_1, A_2, A_3, A_4) = (1, 4, 3, 5)$일 때 생각해보자. $6$개의 레몬을 조건을 만족하게 달 수 있고, $5$개 이하의 레몬으로는 불가능함을 증명할 수 있다. 그러므로 $f(1, 4, 3, 5) = 6$이다.

양의 정수 $N$과 음이 아닌 정수 $B_1, B_2, \cdots, B_N$에 대하여, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• 1 l r k: $B_l, B_{l+1}, \cdots, B_r$에 $k$를 더한다.
• 2 l r : $f(B_l, B_{l+1}, \cdots, B_r)$을 출력한다.

$B_i$의 초깃값은 모두 $0$이다. $2$번 타입의 쿼리마다 답을 출력하면 된다. 매 쿼리 후, $0 \leq B_i \leq 10^9$임이 보장된다.

첫 줄에 $N$과 $Q$가 공백을 사이에 두고 주어진다. 두 번째 줄부터 $Q$개의 줄에 걸쳐, 쿼리가 주어진다. $1 \leq N, Q \leq 2\times10^5$

답을 출력한다.

섭테 : $N, Q \leq 10^3$ (32점) $\\$ $1 \leq N, Q \leq 2\times10^5$ (68점)