题目描述

<w:WordDocument>

<w:View>Normal</w:View>

<w:Zoom>0</w:Zoom>

<w:PunctuationKerning />

<w:DrawingGridVerticalSpacing>7.8 磅</w:DrawingGridVerticalSpacing>

<w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery>

<w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery>

<w:ValidateAgainstSchemas />

<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>

<w:IgnoreMixedContent>false</w:IgnoreMixedContent>

<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>

<w:Compatibility>

<w:SpaceForUL />

<w:BalanceSingleByteDoubleByteWidth />

<w:DoNotLeaveBackslashAlone />

<w:ULTrailSpace />

<w:DoNotExpandShiftReturn />

<w:AdjustLineHeightInTable />

<w:BreakWrappedTables />

<w:SnapToGridInCell />

<w:WrapTextWithPunct />

<w:UseAsianBreakRules />

<w:DontGrowAutofit />

<w:UseFELayout />

</w:Compatibility>

<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>

</w:WordDocument>

<![endif]-->

</p>

<w:LatentStyles DefLockedState="false" LatentStyleCount="156">

</w:LatentStyles>

<![endif]--><!--[if gte mso 10]>

/* Style Definitions */ table.MsoNormalTable {mso-style-name:普通表格; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman"; mso-fareast-font-family:"Times New Roman"; mso-ansi-language:#0400; mso-fareast-language:#0400; mso-bidi-language:#0400;}

<![endif]-->

</p>

在一个小国家中，一个新的小镇终于建成了！如往常一样，Mirko获得了“首席税务巡查员”的职位。他的任务是保证正确地计算各公司的收入情况。一共有N家办公室坐落在主干道上，从左到右被编号为1~N。一开始，所有办公室一开始都是空的。随后，一些公司会搬入或搬出某些办公室。Mirko时不时地会经过某些办公室并审查在这些办公室中，最富有的公司的账目。

一个公司被以如下的方式描述：

T-表示搬入的第一天。

K-表示搬入的办公室的标号。

Z-公司每日的盈利。（可以是负值表示亏损）

S-公司搬入时的公司财务情况。（即公司的账户资金，也可以是负值）

如果一家公司已经在 K 办公室了，当有新公司要进入 K 办公室时，这家公司会立刻搬出。

新公司第一天并不会运营，盈利从第二天开始计算。

Mirko的审查以 3 个整数来描述：

T-审查的时间。

A 和 B-Mirko会检查 A 办公室至 B 办公室（包括A和B）之间的公司。

Mirko只会在一天结束时检查，所有公司这时已经计算完成了当天利润。

 

输入格式

第一行包含 2 个正整数：N（1<=N<=100000）表示办公室的数量和M（1<=M<=300000）表示事件的个数。

接下来 M 行，遵循以下格式：“1 T K Z S”或“2 T A B”（含义如题目描述）。其中 T 会严格递增，并且最后一天小于 1000000,Z 和 S 的绝对值也严格小于 1000000。

（注意A可能大于B）

 

输出格式

对于每次Mirko的审查，每行输出一个整数，表示当天最富有的公司的资产（可以为负）。如果Mirko经过的所有办公室中都没有公司入驻，则输出“nema”（不加引号）。

 

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

-1
nema
7
31
17