DOJ logoDOJ
LoginRegister
DOJ logoDOJ
Call for Tasks
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Problem #12

gift
Authors: pk661
User Contest/Lemon Cup

Statement

Statement language한국어 English

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

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 kkk items for each of the prizes numbered l,l+1,⋯ ,rl, l + 1, \cdots, rl,l+1,⋯,r. However, if k<0k < 0k<0, it means items of each corresponding prize have been discarded.

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

Input

The input is given in the following format.

N QN \ QN Q query1\text{query}_1query1​ query2\text{query}_2query2

Output

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

Constraints

  • 1≤N≤200 0001 \leq N \leq 200\ 0001≤N≤200 000.
  • 1≤Q≤200 0001 \leq Q \leq 200\ 0001≤Q≤200 000.
  • 1≤li≤ ().

Subtasks

#ScoreConstraints
127

N≤1000,Q≤1000N \leq 1000, Q \leq 1000N≤1000,Q≤1000

222

All type 1 queries are given before any type 2 queries are given.

351

No additional constraints.

Samples

Input
5 7 1 1 4 3 1 2 3 1 2 1 4 1 2 2 7 2 1 4 1 2 2 -5 2 1 3
Output
4 -1 6
You must log in to submit.
fact_checkProblem submissionschevron_rightforumProblem boardchevron_right
∣k∣|k|
∣k∣
  • 2 l r: Print the minimum number of gift bundles that can be made by using all the prizes numbered l,l+1,⋯ ,rl, l + 1, \cdots, rl,l+1,⋯,r. At this time, only the prizes numbered l,l+1,⋯ ,rl, l + 1, \cdots, rl,l+1,⋯,r must be used. If it is impossible to make gift bundles using all the prizes, print -1.
  • ​
    ⋮\vdots⋮
    queryQ\text{query}_QqueryQ​

    Each queryi\text{query}_iqueryi​ (1≤i≤Q1 \le i \le Q1≤i≤Q) is in one of the following two formats.

    1 li ri ki1 \ l_i \ r_i \ k_i1 li​ ri​ ki​

    2 li ri2 \ l_i \ r_i2 li​ ri​

    ri≤N1 \leq l_i \leq r_i \leq N
    1≤li​≤ri​≤N
    1≤i≤Q1 \le i \le Q1≤i≤Q
  • −109≤ki≤109-10^9 \leq k_i \leq 10^9−109≤ki​≤109 (1≤i≤Q1 \le i \le Q1≤i≤Q).
  • At any point, the quantity of the iii-th prize will neither become less than 000 nor exceed 10910^9109 (1≤i≤N1 \leq i \leq N1≤i≤N).
  • 2000 ms
    1024 MB
    Checker
    CUSTOM
    [0]