描述

给定一个长度为 n 的数列和 n 个涉及区间加法和区间求和的操作。

输入

• 第一行包含一个整数 n。

• 第二行包含 n 个整数，其中第 i 个整数表示为 a_i，用空格分隔。

• 接下来的 n 行表示查询。每行包含四个整数 opt、l、r 和 c，用空格分隔。

  如果 opt = 0，表示将位于 [l, r] 区间的所有数字都加上 c。

  如果 opt = 1，表示查询位于 [l, r] 区间的所有数字的和，并对结果取模 (c+1)。

输出

对于每次查询，输出一行包含一个整数，表示答案。

样例

输入

4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

输出

1
4

限制

对于100%的数据，1 ≤ n ≤ 50000，且**-2^31 ≤ c, others, ans ≤ 2^31-1**。