分类网络(HardVersion)

题目描述

本题是 L2-分类网络 的困难版本，在本题中，Orange每层分类状态机将改变所有元素的位置而不只是两个，同时，本题在原有的查询操作中，新增了修改操作，也就是说，Orange可以通过操作修改某一层的分类状态机。

Orange设计了一个简单的分类网络，这个网络用于分类信息。网络可以看成是一个由 $m$ 层分类状态机构成的一个集合体，其中每层状态机都接受一个 $n$ 元一维向量，并且输出一个相同大小的向量。状态机构成一个前向传播网络，即第 $i$ 层的输出会作为第 $i+1$ 层的输入。其中，Orange在每层网络中都会对信息进行一次交换，具体为将 $A_i \rightarrow A'_{c_i}$，其中 $c_i$ 为一个 $n$ 元序列，表示将第 $i$ 个元的位置替换到第 $c_i$ 个位置。

例如，假设对于一个 $n=5$ 的向量分类状态机，其分类参数为 $c =[1, 3, 2, 5, 4]$，我们输入一个5维向量 $\vec{A}=(a,b,c,d,e)^T$，则输出的向量 $\vec{A'} = (a, c, b, e, d)$。下图详细展示了一个分类状态机的工作原理:

现在，Orange要分类数据，共询问 $q$ 次操作，操作共分为如下两类：

1. 查询操作 每次会给你输入一个 $n$ 元的向量 $\vec{A}$，并且给你分类网络的入口层 $l$ 和出口层 $r$，你需要输出 $\vec{A}$ 经过 $l \sim r$ 层分类后，最终输出的向量 $\vec{A'}$。 操作指令格式为：

1 l r
A1 A2 A3 ... An

2. 修改操作 每次会给你一个位置 $p$，表示将第 $p$ 层的分类状态机的分类参数 $c_i$ 改成 $c'_i$。 操作指令格式为：

2 p
c1 c2 c3 ... cn

输入格式

输入第一行包含3个整数 $n,m,q$，分别表示向量/状态机大小，分类网络层数与操作次数。 接下来 $m$ 行，每行 $n$ 个整数 $c_i$，表示第 $i$ 层状态机的分类参数。 接下来 $2q$ 行，每2行一条指令，如上题意所述。

数据范围

$1 \le n \le 10$ $1 \le m, q \le 10^5$ $1 \le A_i \le 100$ $1 \le l \le r \le m$ 保证 $c_i$ 构成一个 $n$-排列。

输出格式

对于每次操作1，输出 $n$ 个整数，表示查询的答案。

样例 #1

样例输入 #1

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

样例输出 #1

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

提示

样例解释

对于查询

1 1 1
1 2 3 4 5

向量 $\vec A = (1,2,3,4,5)^T$ 在经过第一层网络后，变成 $\vec A'= (1,3,2,5,4)^T$，具体的过程可以看上文中的图片。