The Unique Contest Problem

You are given a sequence of n sets a₁, a₂, ..., a_n. Initially, every set is empty. The sets are distinct in that they are standard mathematical sets which do not contain duplicate elements.

You need to support the following two types of operations:

1. Update operation: Given three integers l, r and x, for every index i with l ≤ i ≤ r add the element x to the set a_i. Mathematically, for each i in [l, r]:</p>

   \(a_i = a_i \cup {\, x \,}\)

2. Query operation: Given two integers l and r, let S be the union of all sets from a_l to a_r (i.e. S = a_l \cup a_l+1 \cup \cdots \cup a_r), and you must output the sum of all elements in S.

Good luck solving this challenge!

inputFormat

The first line contains two integers n and q (1 ≤ n, q ≤ some small number).

Each of the following q lines describes an operation.

• If the operation is an update, the line will contain four integers: 1 l r x.
• If the operation is a query, the line will contain three integers: 2 l r.

It is guaranteed that the indices use 1-indexing.

outputFormat

For each query operation, print a single line containing the sum of the distinct elements in the union set defined by the query.

sample

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

7
12