Richest Company Inspection

A new town has just been inaugurated in a small country. As usual, Mirko, the newly appointed Chief Tax Inspector, must ensure that every company in town properly handles its accounting. Along the main street there are \(N\) offices numbered from \(1\) to \(N\) from left to right. Initially, all offices are empty. Over time, companies move in and out of these offices. Occasionally, Mirko takes a walk along some offices and checks the account balance of the richest company among those he passes.

Events

• Company Move-in Event: A company moving in is described by four integers:
  • \(T\): The move-in date (the town's inauguration day is \(1\)).
  • \(K\): The office number.
  • \(Z\): The company's daily profit (can be negative if the company is losing money).
  • \(S\): The account balance on the move-in day.
  When a new company moves into office \(K\), if there is already a company there, the old company immediately leaves. Note that the newly moved in company does not start operating (i.e. earning profit) until the day after move-in.
• Inspection Event: Mirko's inspection is described by three integers:
  • \(T\): The inspection date (the town's inauguration day is \(1\)).
  • \(A, B\): Mirko will walk past all offices in the interval \([A, B]\).
  Since Mirko works at the end of the day, by the time he takes his walk all companies have finished business for the day and their profits have been added to their accounts. During an inspection, update all companies in the specified range to include the profit for the day, and then output the largest account balance. If no office in the range is occupied, output 0.

  inputFormat

  The first line consists of two integers \(N\) and \(Q\), where \(N\) is the number of offices and \(Q\) is the number of events.

  Each of the next \(Q\) lines represents an event. An event is of one of the following two forms:

  • 1 T K Z S — A company moves in on day \(T\) into office \(K\) with daily profit \(Z\) and initial account balance \(S\). If office \(K\) is already occupied, the current company is replaced before the new company moves in. The new company will start earning profit from day \(T+1\).
  • 2 T A B — On day \(T\), Mirko inspects offices \([A, B]\) after all companies have updated their accounts for the day. Your task is to output the maximum account balance among these offices (or 0 if none are occupied).

  You can assume that the events are given in non‐decreasing order of \(T\).

  outputFormat

  For each inspection event, output a single line containing the maximum account balance among the inspected offices. If there is no company in the range, output 0.

  sample

  3 5
  1 1 1 10 100
  1 2 2 5 50
  2 3 1 2
  1 4 1 7 80
  2 5 1 3
  

  120
  87

  </p>