T137198 zhlTao Limit singErcoder

有一天 Limit 问了 Singercoder 一个问题： 定义函数 $f(x) = 1 ⨁ 2 ⨁ ... ⨁ x$，那么对于一个 $x$ 如何快速的给出这个函数的值。 Singercoder 苦思冥想，终于在一个不眠之夜，想到了神奇的方法，解决了这个问题。 然而 Limit 神并不能满足，他要给 Singercoder 一个数列$\{a_i\}$ 然后区间修改这个序列，并区间查询这个序列的 $f(a_i)$之和。Limit 承认自己能轻松解决这个问题，而剩下两个人都在 fake，你能用自己巧妙的思路证明这只是一道水题，并以此来戳破他们的伪装吗？

Limit 给了你一个长度为 $n$ 数列 $a_i$，然后给你 $m$ 次操作。 操作有两种 1. 形如 `1 l r x` 表示对于 $[l,r]$ 的范围的 $a_i$ 均加一个 $x$ 2. 形如 `2 l r` 表示查询 $\sum _{i=l}^{r} f(a_i)$ 其中 $f(x) = 1 ⨁ 2 ⨁ ... ⨁ x$

第一行一个正整数 $n$ 第二行 $n$ 个非负整数 ，第 $i$ 个整数是 $a_i$ 第三行是一个正整数 $m$ 接下来的 $m$ 行，每行第一个数是 $1$ 或 $2$ 若为 1 则接下来有三个整数 $l,r,x$ 表示将 $[l,r]$ 之间的 $a_i$ 均加上 $x$ 若为 2 则接下来有两个整数 $l,r$ 表示查询 $\sum _{i=l}^{r} f(a_i)$ 相邻的数用一个空格隔开

对于每一次操作 2 输出一行一个整数，表示答案

对于 $10\%$ 的数据 $2\le n,m \le 10$ 对于 $30\%$ 的数据 $2\le n,m \le 1000$ 对于 $60\%$ 的数据 $2\le n,m \le 10000$ 对于 $100\%$ 的数据 $2\le n,m \le 1000000$， 初始时 $0 \le a_i \le 32767$ 对于每次操作 1 时 $0 \le x \le 32767$。 满足 $1\le l_i \le r_i \le n$ 题目 idea 由 [Limit](https://www.luogu.com.cn/user/86625) 想出，std 是 [zhltao](https://www.luogu.com.cn/user/232125) 给出，验题人和提供数据者是 [Singercoder](https://www.luogu.com.cn/user/239241) PS(其实后五个点是zhltao造的。) **数据不卡常** 由于读入数据过大，请使用**快速**的IO方法。保证数据合法。且是 `rand( )` 函数生成。