34259번 - 레몬컵 상품 준비하기 서브태스크

레몬컵 운영진은 대회 상품을 준비하려 한다. 상품의 종류는 총 $N$개이며, 각 종류는 $1$번부터 $N$번까지 번호가 매겨져 있다. 처음에는 모든 상품의 개수가 $0$이다.

재원이는 이 상품들을 이용해 선물 묶음을 만들고자 한다. 하나의 선물 묶음은 연속한 번호의 상품을 $\mathbf{2}$개 이상 포함해야 하며, 각 상품은 정확히 $\mathbf{1}$개씩 사용한다.

다음과 같은 두 가지 쿼리가 주어진다.

• 1 l r k: $l, l+1, \dots, r$번 상품을 각각 $k$개씩 구매한다. 단, $k < 0$이면 해당 상품들을 각각 $|k|$개씩 폐기하였다는 뜻이다.
• 2 l r: $l, l+1, \dots, r$번 상품을 모두 사용하여 만들 수 있는 선물 묶음의 최소 개수를 출력한다. 이때 $l, l+1, \dots, r$번 상품만을 사용해야 한다. 만약 모든 상품을 사용해서 선물 묶음을 만들 수 없다면 -1을 출력한다.

$2$번 쿼리가 주어질 때마다 정답을 출력하라.

입력은 다음과 같은 형식으로 주어진다.

$N \ Q$

$\text{query}_1$

$\text{query}_2$

$\vdots$

$\text{query}_Q$

각각의 $\text{query}_i$ ($1 \le i \le Q$)는 다음 두 형식 중 하나이다.

$1 \ l_i \ r_i \ k_i$

$2 \ l_i \ r_i$

$2$번 쿼리가 주어질 때마다 정답을 출력한다.

• $1 \leq N \leq 200\ 000$.
• $1 \leq Q \leq 200\ 000$.
• $1 \leq l_i \leq r_i \leq N$ ($1 \le i \le Q$).
• $-10^9 \leq k_i \leq 10^9$ ($1 \le i \le Q$).
• 어떤 시점에서도 $i$번 상품의 개수는 $0$ 미만이 되거나 $10^9$를 초과하지 않는다 $(1 \leq i \leq N)$.