501000043 - 早凉爱旅行2
早凉的故乡紫猫国可以用一个 n\times n 的网格图来表示。每一个网格就是一个城市。
为了方便，我们用 (x,y) 表示第 x 行第 y 列的网格。
网格 (x,y) 有权值 a_{x,y}，且有计算公式 a_{x,y}=\max(x,y)，其中 \max(x,y) 表示 x,y 中最大数。
若两个网格 (x,y),(x^\prime,y^\prime) 满足 |x-x^\prime|+|y-y^\prime|=1，我们称这两个网格相邻。
紫猫国还有 2n-2 个正整数参数，为： x_1,x_2,\cdots,x_{n-1},y_1,y_2,\cdots,y_{n-1}。且对于任意正整数 i(1\leq i < n)，1\leq x_i,y_i\leq i。
网格之间有连双向道路，规则如下：
- 若两个网格 (x,y),(x^\prime,y^\prime) 相邻且满足 a_{x,y}=a_{x^\prime,y^\prime}，则 (x,y),(x^\prime,y^\prime) 之间有连双向道路。
- 对于任意正整数 i(1\leq i < n)，(i,x_i),(i+1,x_i) 之间有连双向道路。
- 对于任意正整数 i(1\leq i < n)，(y_i,i),(y_i,i+1) 之间有连双向道路。
早凉会在紫猫国留 m 天，在第 i 天中，会发生下列事件之一：
1 a b c表示 x_a 的值修改为 b，y_a 的值修改为 c。2 a b c d表示早凉将从 (a,b) 出发，去 (c,d)，你需要帮她计算这次旅行最少要走几条双向道路。
早凉只用 \text{373ms} 就算出来了，你能教她一个更优解吗？
输入
第一行两个正整数 n,m。
第二至 n 行，第 i+1 行两个正整数 x_i,y_i。
第 n+1 至 n+m 行，第 n+i 行首先一个数 \text{opt}_i，表示第 i 天发生的事件类型。若 \text{opt}_i=1，则后面三个数 a,b,c，若 \text{opt}_i=2，则后面四个数 a,b,c,d。
输出
对于每个 \text{opt}_i=2 的事件，分行输出答案。
样例
输入
4 7 1 1 1 2 2 1 2 2 4 4 3 2 4 4 3 3 2 1 2 3 3 2 2 2 4 4 2 1 4 2 3 1 3 1 1 2 4 4 3 3
输出
3 4 3 6 2 6
提示
4\leq n\leq 2\times10^5,1\leq m\leq 2\times10^5。
保证任意时刻，对于任意正整数 i(1\leq i < n)，1\leq x_i,y_i\leq i。
| 子任务编号 | 分值 | n | m | 特殊性质 |
|---|---|---|---|---|
| \text{Subtask}1 | 10 | \leq100 | \leq2\times10^3 | 无 |
| \text{Subtask}2 | 10 | \leq100 | \leq2\times10^5 | A |
| \text{Subtask}3 | 10 | \leq2\times10^3 | \leq2\times10^3 | 无 |
| \text{Subtask}4 | 20 | \leq2\times10^5 | \leq2\times10^5 | AB |
| \text{Subtask}5 | 20 | \leq2\times10^5 | \leq2\times10^5 | A |
| \text{Subtask}6 | 20 | \leq2\times10^5 | \leq2\times10^5 | B |
| \text{Subtask}7 | 10 | \leq2\times10^5 | \leq2\times10^5 | 无 |
特殊性质 A: 对于任意正整数 i(1\leq i\leq m)，\text{opt}_i=2 。
特殊性质 B: 保证任意时刻，对于任意正整数 i(1\leq i < n)，x_i=y_i。