The organizers of the Lemon Cup are planning to prepare prizes for the contest. There are $N$ types of prizes in total, and each type is numbered from $1$ to $N$. Initially, the quantity of every prize is $0$.

Jaewon wants to use these prizes to create gift bundles. A single gift bundle must contain two or more consecutively numbered prizes, and exactly one prize of each included type is used.

The following two types of queries are given.

• 1 l r k: Purchase $k$ items for each of the prizes numbered $l, l + 1, \cdots, r$. However, if $k < 0$, it means $|k|$ items of each corresponding prize have been discarded.
• 2 l r: Print the minimum number of gift bundles that can be made by using all the prizes numbered $l, l + 1, \cdots, r$. At this time, only the prizes numbered $l, l + 1, \cdots, r$ must be used. If it is impossible to make gift bundles using all the prizes, print -1.

Every time a type 2 query is given, print the answer of the query.

The input is given in the following format.

$N \ Q$ $\text{query}_1$ $\text{query}_2$ $\vdots$ $\text{query}_Q$

Each $\text{query}_i$ ($1 \le i \le Q$) is in one of the following two formats.

$1 \ l_i \ r_i \ k_i$

$2 \ l_i \ r_i$

Every time a type 2 query is given, print the answer of the query, separated by new line.

• $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$).
• At any point, the quantity of the $i$-th prize will neither become less than $0$ nor exceed $10^9$ ($1 \leq i \leq N$).