众所周知，某些数据结构可以实现数组的子区间位置翻转功能，智乃现在有以下几种区间操作，她想让你编写一种数据结构实现这几个功能。

1、数组子区间位置翻转，即对于一个数组区间，反转后变为

2、子区间内所有元素加上，即

3、子区间内所有元素乘以，即

4、求区间元素之和对取余数的结果。

对于一个长度为的数组所有长度为的子区间，有且仅有个子区间，分别为，我们按照顺序称其为第个长子区间，第个长子区间的左端点为，右端点为。

智乃现在对这个子区间非常感兴趣，所以她决定依次对这些数组区间进行操作，具体来讲，她将会进行次数组操作，且第次操作的子区间左端点为上文中提到的，右端点为上文中的

输入描述:

第一行输入两个正整数表示数组区间的大小，子区间的长度。

由于数据量较大，故采取前个数据从外部输入，后个数据按照某种方式生成。

接下来输入一个正整数表示数组的前个数据。

接下来一行输入个整数表示的值。

对于后个未确定的元素，按照（数组的下标从开始计算）的方式依次确定它们的值。

接下来还需要确定个操作的内容。

由于数据量较大，故采取前个操作从外部输入，后个操作按前个操作循环的模式。

接下来首先输入一个正整数

接下来行首先输入一个正整数表示操作。

根据操作数不同，表示不同的含义。

若表示需要对第个子区间执行区间元素翻转的操作

若，则还需输入一个整数表示对第个子区间执行区间元素加上的操作。

若，则还需输入一个整数表示对第个子区间执行区间元素乘以的操作。

若，则需要查询第个子区间元素之和对取余数的结果。

输出描述:

为了避免输出量过大，请按照如下方式整合所有查询的答案后仅输出一个整数。

记每一个，区间元素之和对余数的结果为。

请输出（假设有次查询操作）。

其中表示位运算异或。

5 2
5
1 2 3 4 5
4
1
4
3 10
4

41

共个操作

先反转，变为

然后求和，答案为

每个数乘以，变为

求和，答案为

输出

1000 1000
5
121439503 385390597 407275895 920845453 338014658
1
4

5926922

备注:

请注意本题为非常见模数，题目保证它是一个质数。