Background

小E 是一位实力强大的OIer，经常在各类比赛中随手AK 虐场。然而她最近秒题时遇到了
一道需要她思考15 秒才能做出的题目，整整花了15 倍于其他题目的时间。她认为这个问题
十分有意思，并且对其进行了一些拓展和修改以后抛给了你。你能接受小E 的挑战吗？

Description

Format

Input

输入的第1 行包含两个整数n,q，n表示序列长度，q 表示操作次数。
接下来1 行，包含n 个整数，其中第i 个表示ai。
接下来1 行，包含n 个整数，其中第i 个表示wi。
接下来q 行，每行包含4 个或3 个整数，其中第1 个整数表示操作类型（见题目描述）。
对于第1 种操作，接下来3 个整数依次表示l,r,k ；对于第2 或第3 种操作，接下来2 个整数
依次表示p,k 。

Output

对于每个第1 种操作输出一行一个整数，表示答案。

Sample 1

Input

10 10
13 15 23 45 21 23 14 26 35 44
12 32 15 47 15 32 12 47 32 32
1 2 8 17
2 4 26
1 1 6 47
3 9 6
2 9 4
1 1 7 5
3 7 6
2 7 2
3 3 6
1 4 9 6

Output

4294966372
4294964016
4294967160
4294967229