Description
从前有一个贸易市场，在一位执政官到来之前都是非常繁荣的，自从他来了之后，发布了一系列奇怪的政令，导致贸易市场的衰落。
有
个商贩，从
编号，每个商贩的商品有一个价格
，有两种政令；同时，有一个外乡的旅客想要了解贸易市场的信息，有两种询问方式：
-
（政令），对于
-
（政令），对于
-
（询问）给定 ，求
-
（询问）给定 ，求
Input
第一行为两个空格隔开的整数
分别表示商贩个数和政令 + 询问个数。
第二行包含
个由空格隔开的整数
接下来
行，每行表示一个操作，第一个数表示操作编号
，接下来的输入和问题描述一致。
Output
对于每个 3、4 操作，输出询问答案。
Sample Input
10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9
Sample Output
-2
-2
-2
-2
0
1
1
HINT
对于
的数据，
；
对于
的数据，保证数据随机；
对于
的数据，