#12 gift

Loading problem...

Preparing the statement, recent submissions, and submit form.

#12 gift | DOJ

Authors: pk661

Statement

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

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

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

1 l r k: $l, l + 1, \cdots, r$ 번 상품을 각각 $k$ 개씩 구매한다, 단, $k < 0$ 이면 해당 상품들을 각각 $|k|$ 개씩 폐기하였다는 뜻이다.
2 l r: $l, l + 1, \cdots, r$ 번 상품을 모두 사용하여 만들 수 있는 선물 묶음의 최소 개수를 출력한다. 이때 $l, l + 1, \cdots, 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$ 번 쿼리가 주어질 때마다 정답을 출력한다.

Input

Output

4
-1
6