Under construction

Still being built. Things may change

Richest Tenant Company

Time limit5sMemory limit128 MB

Summary
Process chronological move-ins and range-max inspections on offices where each company's wealth grows linearly with time, requiring a segment tree over linear functions evaluated at the query day.
Level

Hard8 of 10

Topics
Segment tree, Intervals, Implementation
Solved
No attempts yet

Problem

There are N offices, numbered 1 through N from left to right. Initially, every office is empty.

When a company moves in, the following information is given.

  • T: the move-in day. The first day of the office business is day 1.
  • K: the office number
  • Z: the amount the company earns or loses per day. This value may be negative.
  • S: the amount of money the company has on its move-in day

If a new company moves into an office K that is already occupied, the previous company leaves that office on that day. A company spends its entire move-in day moving, so it earns no profit on that day. After that, while the company remains in the office, its money changes by exactly Z after work each day. Therefore, if a company moves in on day T0 with S money and is still in the same office after work on day D, its money is S + (D - T0) × Z.

Sometimes a continuous office interval is inspected to find the richest company in it. The interval has offices A and B as endpoints, and A may be greater than B. Each inspection is made after all work for that day has finished.

Given all move-in and inspection events in chronological order, answer every inspection.

Input

The first line contains the number of offices N and the number of events M. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000)

Each of the next M lines describes one event in chronological order.

  • Company move-in: 1 T K Z S
  • Inspection: 2 T A B

At most one event happens on any day, so T is always given in increasing order. The day of the last event is less than 1,000,000. The absolute values of Z and S are also each less than 1,000,000.

Output

For each inspection, print one line containing the largest amount of money held by any company in the inspected interval. If no company occupies an office in that interval, print nema.

Examples3

  1. Example 1

    Input
    2 4
1 1 1 2 4
1 2 2 3 2
2 5 1 2
2 7 1 2
    Expected output
    12
17

  2. Example 2

    Input
    3 6
1 1 1 4 -2
1 2 2 2 6
2 3 3 1
2 4 3 1
1 5 3 -6 20
2 6 2 3
    Expected output
    8
10
14

  3. Example 3

    Input
    5 9
1 1 5 4 -5
2 2 3 5
1 3 4 6 9
2 4 1 2
1 6 2 2 3
2 8 2 1
1 9 4 0 17
2 10 5 5
2 11 1 4
    Expected output
    -1
nema
7
31
17