我们定义 $B(x)$ 为 $x$ 的二进制表示中数字 1 的个数。例如，$B(7) = B((111)_2) = 3$，$B(8) = B((1000)_2) = 1$，$B(9) = B((1001)_2) = 2$。

我们定义 $F(x) = \min \{ y \mid (y > x) \land (B(y) \le B(x)) \}$。例如，$F(4) = 8, F(5) = 6, F(6) = 8$。

Zayin 有一片森林（一组树），其节点编号从 1 到 $n$。对于每个节点（例如节点 $x$），如果 $F(x)$ 不大于 $n$，则节点 $x$ 的父亲是 $F(x)$，否则节点 $x$ 是一棵树的根。

我们用 $A[i]$ 表示节点 $i$ 上的苹果数量。初始时，所有的 $A[i]$ ($1 \le i \le n$) 均为 0。为了让他的女朋友开心，Zayin 将在树上施展魔法。魔法包含两种操作：

1. Add $x$ $v$：对于节点 $x$ 的每一个祖先（包括其自身），在其上增加 $v$ 个苹果。换句话说，对于节点 $x$ 到其所在树的根路径上的每一个节点（例如节点 $y$），令 $A[y] = A[y] + v$。
2. Sum $L$ $R$：统计索引在 $L$ 和 $R$ 之间的节点上的苹果总数。换句话说，你需要计算 $\sum_{i=L}^{R} A[i]$。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^{18}, 1 \le m \le 10^5$)，其中 $n$ 是节点数，$m$ 是操作数。

接下来的 $m$ 行按顺序描述了 $m$ 个操作。每行包含三个整数。第一个整数是 $op$。如果 $op = 1$，则接下来的两个整数是 $x$ 和 $v$，表示一次 Add 操作。如果 $op = 2$，则接下来的两个整数是 $L$ 和 $R$，表示一次 Sum 操作。($1 \le x \le n, 1 \le v \le 10^9, 1 \le L \le R \le n$)

输出格式

对于每次 Sum 操作，输出一行，包含一个数字，表示相应的计算结果。

样例

输入 1

8 6
1 1 1
1 3 2
1 5 3
1 7 4
2 1 5
2 4 8

输出 1

10
23

输入 2

1000000000000000000 2
1 1 1
2 1 1000000000000000000

输出 2

60