题目描述

这是一道模板题。

给你两个序列 $K_i$ 和 $B_i$，要求支持在线进行如下操作：

1. 给 $X > 0$，对于每个 $B_i$，变成 $B_i + K_iX$。

2. 给 $L, R, Y$，求出在 $i \in [L, R]$ 中第 $Y$ 大的 $B_i$ 值。

3. 修改一组 $K_i, B_i$。

输入格式

第一行输入两个正整数 $N, Q$。

接下来一行，输入 $N$ 个整数表示 $K_i$。

接下来一行，输入 $N$ 个整数表示 $B_i$。

接下来共 $Q$ 行，每行首先输入一个整数表示操作编号，分别有以下三种情况：

• $1\ X$
• $2\ L\ R\ Y$
• $3\ i\ k\ b$

输出格式

对于每个 $2$ 询问，输出一个整数表示答案。

样例

input

3 10
-1 3 1
1 -3 0
2 1 3 1
2 1 3 2
2 1 3 3
1 1
2 1 3 1
2 1 3 2
2 1 3 3
3 2 0 2
2 2 3 1
2 2 3 2

output

1
0
-3
1
0
0
2
1

数据范围与提示

对于 $100\%$ 的数据，保证 $1\le N, Q\le 2\times 10^5; 1\le Y \le \min(R - L + 1, 30); X, |K_i| \le 10^6, |B_i| \le 10^{18}$。