Description

OceanCat通过卖废品、送外卖积攒了一点点钱，他认为如果不是为了学算法自己也没有机会去攒到钱，所以他决定回报那些帮助过他的人，他要邀请所有帮助过他学习算法的人一起团建，一起来玩 大 富 翁 ！OceanCat首先要给他们每个人100元，随后他拿出了一枚硬币和两个好多好多好多面的“骰子”，然后开始抛硬币。如果硬币抛出了正面，那么他将会同时转动两个“骰子“摇出来两个数，先停止转动的”骰子“上展示的数字作为编号，后停止转动的”骰子“上展示的数字作为资金增量(资金增量可能为负，毕竟OceanCat也没有那么多钱一直往上加)。如果硬币抛出了反面，他还是会同时转动两个“骰子“摇出来两个数，先停止转动的”骰子“上展示的数字作为编号a，后停止转动的”骰子“上展示的数字作为编号b。随后他会随机选择一个人去询问编号在[a,b)的人之间资金最多的有多少，资金最少的又有多少(存在欠钱的情况，但如果在结束后还是欠钱的状态OceanCat也不会向你索要这部分钱)，因为他想要在团建结束后向资金最多的朋友表示祝贺，向资金最少的朋友进行额外添补，由于选择是随机的，所以他每次都可能选到你进行回答，如果回答错误会有很严重的惩罚(指吃冰淇淋)，而你刚好很不喜欢吃冰淇淋对吧(doge)，所以你需要随时计算好这两个数字。(至于OceanCat为什么不自己算，众所周知，OceanCat的算术水平甚至不如陆小果

Input Format

第一行输入两个整数n,m，表示OceanCat一共邀请了n个人编号为1-n，并且会抛m次硬币(1≤n,m≤100000)。

接下来m行，首先输入一个数字，

如果输入的数字为1，表示硬币抛出了正面，那么就会再输入两个数k和x，k表示先停止转动的”骰子“上展示的数字，x表示后停止转动的”骰子“上展示的数字(1≤k≤n，-100000≤x≤100000)

如果输入的数字为2，表示硬币抛出了反面，那么就会再输入两个数a和b，分别表示先停止转动的“骰子”上的编号和后停止转动的“骰子”上的编号，那么这时候你就需要计算好这两个数字来应对OceanCat的提问了。

Output Format

对于每次硬币抛出反面时，输出一行两个数字表示如果提问到你你将要回答的结果，两个数字间以空格隔开

3 3
1 1 50
1 3 -100
2 1 3​

150 100​

Hint

保证所有输入一定合法

对于抛出正面向上后，两个”骰子“如果同时停转那么就重新转一次...

对于抛出反面向上后，两个“骰子”的点数如果满足a≥b，那么就重新转一次...

Source

数据结构 签到