CF380B.Sereja and Tree

Sereja adores trees. Today he came up with a revolutionary new type of binary root trees.

His new tree consists of n levels, each vertex is indexed by two integers: the number of the level and the number of the vertex on the current level. The tree root is at level 1, its index is (1, 1). Here is a pseudo code of tree construction.

//the global data are integer arrays cnt[], left[][], right[][]

cnt[1] = 1;
fill arrays left[][], right[][] with values -1;
for(level = 1; level < n; level = level + 1){
cnt[level + 1] = 0;
for(position = 1; position <= cnt[level]; position = position + 1){
if(the value of position is a power of two){ // that is, 1, 2, 4, 8...
left[level][position] = cnt[level + 1] + 1;
right[level][position] = cnt[level + 1] + 2;
cnt[level + 1] = cnt[level + 1] + 2;
}else{
right[level][position] = cnt[level + 1] + 1;
cnt[level + 1] = cnt[level + 1] + 1;
}
}
}

After the pseudo code is run, cell cnt[level] contains the number of vertices on level level. Cell left[level][position] contains the number of the vertex on the level level + 1, which is the left child of the vertex with index (level, position), or it contains -1, if the vertex doesn't have a left child. Similarly, cell right[level][position] is responsible for the right child. You can see how the tree with n = 4 looks like in the notes.

Serja loves to make things complicated, so he first made a tree and then added an empty set A(level, position) for each vertex. Then Sereja executes m operations. Each operation is of one of the two following types:

• The format of the operation is "1 t l r x". For all vertices level, position (level = t; l ≤ position ≤ r) add value x to set A(level, position).
• The format of the operation is "2 t v". For vertex level, position (level = t, position = v), find the union of all sets of vertices that are in the subtree of vertex (level, position). Print the size of the union of these sets.

Help Sereja execute the operations. In this problem a set contains only distinct values like std::set in C++.

Sereja 非常喜爱树。今天，他提出了一种革命性的新型二叉根树。

他的新树共有 $n$ 层，每个顶点由两个整数索引：所在层数与该层上的顶点编号。树的根节点位于第 $1$ 层，其索引为 $(1,\,1)$。以下是该树的伪代码构造过程：

// 全局数据为整型数组 cnt[], left[][], right[][]

cnt[1] = 1;
将数组 left[][] 和 right[][] 的所有元素初始化为 -1;
for(level = 1; level < n; level = level + 1){
cnt[level + 1] = 0;
for(position = 1; position <= cnt[level]; position = position + 1){
if(position 的值是 2 的幂次) { // 即 1, 2, 4, 8...
left[level][position] = cnt[level + 1] + 1;
right[level][position] = cnt[level + 1] + 2;
cnt[level + 1] = cnt[level + 1] + 2;
}else{
right[level][position] = cnt[level + 1] + 1;
cnt[level + 1] = cnt[level + 1] + 1;
}
}
}

伪代码执行完毕后，数组单元 cnt[level] 存储第 level 层的顶点总数；数组单元 left[level][position] 存储顶点 $(level,\,position)$ 的左子节点在第 level + 1 层中的编号（若该顶点无左子节点，则存为 -1）；类似地，right[level][position] 负责记录右子节点。你可在“注释”部分查看 $n = 4$ 时该树的具体形态（图片链接保持不变）。

Sereja 喜欢把事情复杂化，因此他首先构建了这样一棵树，然后为每个顶点 $(level,\,position)$ 添加一个空集合 $A(level,\,position)$。接着，Sereja 执行 $m$ 个操作。每个操作属于以下两种类型之一：

• 操作格式为 "1 t l r x"：对所有满足 $level = t$ 且 $l \leq position \leq r$ 的顶点 $(level,\,position)$，将值 $x$ 加入集合 $A(level,\,position)$。
• 操作格式为 "2 t v"：对顶点 $(level,\,position)$（其中 $level = t$，$position = v$），求出其子树中所有顶点对应集合的并集，并输出该并集的大小。

请帮助 Sereja 执行这些操作。本题中，“集合”仅包含互异的元素，其语义等同于 C++ 中的 std::set。

The first line contains integers n and m (1 ≤ n, m ≤ 7000).

Next m lines contain the descriptions of the operations. The operation of the first type is given by five integers: 1 t l r x (1 ≤ t ≤ n; 1 ≤ l ≤ r ≤ cnt[t]; 1 ≤ x ≤ 106). The operation of the second type is given by three integers: 2 t v (1 ≤ t ≤ n; 1 ≤ v ≤ cnt[t]).

第一行包含两个整数 $n$ 和 $m$（$1 ≤ n, m ≤ 7000$）。

接下来 $m$ 行描述操作。第一类操作由五个整数给出：1 t l r x（其中 $1 ≤ t ≤ n$；$1 ≤ l ≤ r ≤ \text{cnt}[t]$；$1 ≤ x ≤ 10^6$）。第二类操作由三个整数给出：2 t v（其中 $1 ≤ t ≤ n$；$1 ≤ v ≤ \text{cnt}[t]$）。

For each operation of the second type, print the answer on a single line.

对于每个第二类操作，在单独一行中输出答案。

You can find the definitions that are used while working with root trees by this link: http://en.wikipedia.org/wiki/Tree_(graph_theory)

You can see an example of a constructed tree at n = 4 below.

有关根树相关定义，请参见此链接：http://en.wikipedia.org/wiki/Tree_(graph_theory)

下方展示了 $ n = 4 $ 时构造出的一棵示例树。