Background

Special for beginners, ^_^

Description

给定 n 个数的序列 a。m 次操作，操作有两种：

1. 1.求 l 到 r 的和
2. 把 l 到 r 的数异或 x;

​1≤n≤1e5 ，1≤m≤5×1e4 ，0≤ai≤1e6, 1≤x≤1e6

Format

Input

第一行输入 n 代表有 n 个数 第二行输入 ai 第三行输入 m 接下来 m 行 表示操作或者询问 （1 l r ) 表示操作1 （2 l r x) 表示操作2

Output

Samples

5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3

26
22
0
34
11

Limitation

500ms, 1024KiB for each test case.