Ai Hoshino gives you an undirected graph $G$. Let $R(i)$ be the multiset of the other endpoints of all edges connected to $i$. The graph may contain multiple edges but no self-loops.

Each node has a weight $w_i$, initially $0$. You need to maintain two types of operations:

• 1,l,r,v: For all $i \in [l, r]$ and $j \in R(i)$, update $w_j = w_j + v$.
• 2,l,r: Calculate $\sum_{i \in [l, r]} \sum_{j \in R(i)} w_j$.

The output values should be taken modulo $2^{64}$.

Input

The first line contains three integers $n, m, q$.

The next $m$ lines each contain two integers $u, v$, representing an edge.

The next $q$ lines each contain three or four integers representing an operation.

Output

For each operation of type 2, output the calculated result on a new line.

Examples

Input 1

6 6 5
2 6
6 1
5 3
1 5
3 1
2 4
1 1 6 1
1 2 4 3
1 3 4 3
2 3 6
2 1 2

Output 1

53
24

Subtasks

Idea: Larunatrecy, Solution: Larunatrecy, Code: Larunatrecy, Data: Larunatrecy

For $20\%$ of the data, $1 \leq n, m, q \leq 5000$.

For $40\%$ of the data, $1 \leq n, m, q \leq 5 \times 10^4$.

For an additional $10\%$ of the data, $l = r$ always holds.

For $100\%$ of the data, $1 \leq n, m, q \leq 2 \times 10^5, 0 \leq v \leq 10^9$.