插花

题目描述

一共$n$个花瓶，一开始所有花瓶都没有花，每个瓶子最多插$1$朵花。维护如下两种操作$m$次：

1. 插花：给定$x$朵花，并给定位置$p$，从第$p$个花瓶开始，向右依次插花，遇到有花的瓶子跳过，没有的则插入一朵。若到了最后一个瓶子，花还没用完，则忽略剩下的花。插花后报告第一个插入花和最后一个插入花的瓶子。特别的，若从$p$ 开始到最后无一个空瓶，则报告$-1$。
2. 制作花束：给定范围$[l,r]$，将$[l,r]$ 中所有的花取出做成一束花束，该操作会清空范围内所有的花瓶。报告花束大小，即包含多少朵花。

输入格式

本题有多组测试用例 第一行输入一个T，代表有测试用例的数量 第二行输入两个整数 $n$,$m$ ,分别表示花瓶的数量和操作次数 接下来$m$行，每行三个整数，其中有两种情况：

• 对于第一个整数$k$如果是$1$,那么后面两个整数$p$,$x$，表示操作一中从第$p$个花瓶开始插花，插$x$朵花
• 对于第一个整数$k$如果是$2$,那么后面两个整数$l$,$r$,表示操作二中的范围

数据范围

$1≤n,m,p≤10^5$ ， $1≤l≤r≤10^5$ ,$0≤x≤10^9$

输出格式

每次询问输出一个答案，占一行。

样例 #1

样例输入 #1

1
10 5
1 3 5
2 4 5
1 1 8
2 3 6
1 8 8

样例输出 #1

3 7
2
1 9
4
-1