题目描述

你有一棵长度为 $n$ 的线段树。

以下给出本题中线段树的定义。该定义可能与你熟悉的线段树有所不同。

• 线段树是一棵有根二叉树，每个节点对应序列上的一个区间 $[l,r]$，根节点对应区间 $[1,n]$。
• 对于一个表示区间 $[l,r]$ 的节点：
  • 若 $r-l=0$，则该节点为叶节点；
  • 否则，存在一个整数 $m$，满足 $l\le m<r$，其左儿子表示区间 $[l,m]$，右儿子表示区间 $[m+1,r]$。
• 线段树的形态取决于每个非叶节点所选择的划分点 $m$。

你需要进行 $q$ 次修改或询问。

每次修改会对树中的一个局部结构进行左旋或右旋，其形式如下图所示：

旋转时：

• 子树 $A,B,C$ 内部不会发生任何变化；
• 子树 $A,B,C$ 以及节点 $X,Y$ 的相对位置会改变；
• 节点 $X,Y$ 所表示的区间会改变。

每次询问给定一个区间，要求计算该区间至少可以由多少个线段树节点所表示的区间直接相加得到。

输入格式

从文件 entrench.in 中读入数据。

第一行包含三个整数 $n,q,\mathrm{type}$，分别表示线段树长度、修改与询问的总数，以及是否强制在线。

接下来 $2n-1$ 行，第 $i$ 行包含四个整数

$$l_i,\ r_i,\ L_i,\ R_i,$$

分别表示编号为 $i$ 的线段树节点所表示区间的左端点、右端点、左儿子编号和右儿子编号。若某个儿子不存在，则对应编号为 $0$。

保证：

• 叶节点编号不小于 $n$；
• 非叶节点编号小于 $n$。

接下来 $q$ 行，每行包含一个操作，格式如下。

修改操作

1 x

表示以节点 $x$ 及其父节点为轴进行旋转：

• 若 $x$ 为根节点，忽略本次操作；
• 若 $x$ 是其父节点的左儿子，进行右旋；
• 若 $x$ 是其父节点的右儿子，进行左旋。

查询操作

2 l r

表示查询区间 $[l,r]$。若 $l>r$，则交换 $l,r$。

强制在线规则

输入中的操作参数是加密后的 $x',l',r'$，实际参数按下式计算：

$$x=(x'+\mathrm{lastans}\times\mathrm{type})\bmod(n-1)+1,$$$$l=(l'+\mathrm{lastans}\times\mathrm{type})\bmod n+1,$$$$r=(r'+\mathrm{lastans}\times\mathrm{type})\bmod n+1.$$

其中，$\mathrm{lastans}$ 表示上一次查询的答案，初始时

$$\mathrm{lastans}=0.$$

输出格式

输出到文件 entrench.out 中。

对于每个查询操作，输出一行一个整数，表示答案。

样例 1

输入

4 2 0
1 4 2 7
1 3 3 6
1 2 4 5
1 1 0 0
2 2 0 0
3 3 0 0
4 4 0 0
1 2
2 1 3

输出

2

数据范围与约定

对于全部测试数据：

$$n,q\ge 1.$$

测试点	$n$ 不超过	$q$ 不超过	是否在线	是否有修改	空间限制
1	$1000$		否	否	512 MB
2			是
3			否	是
4			是
5～8	$200000$		否	否
9			是
10～11					64 MB
12			否	是	512 MB
13					64 MB
14					32 MB
15～16			是		512 MB
17					64 MB
18～20					32 MB