해결한 사람
0
명
정답률
0.00
%
시간 제한
4000
ms
메모리 제한
977
MB
Nikita and Sasha는 마법 생물들을 번식시켜야 하는 컴퓨터 게임을 한다. 처음에는 1부터 k까지 번호가 매겨진 k마리의 생물이 있다. 생물은 n개의 서로 다른 특성을 가진다.
Sasha에게는 주어진 두 생물로 새로운 생물을 만들 수 있는 주문이 있다. 새 생물의 각 특성은 사용한 생물들의 대응하는 특성 중 최댓값과 같다. Nikita에게도 비슷한 주문이 있지만, 그의 주문으로 만든 새 생물의 각 특성은 사용한 생물들의 대응하는 특성 중 최솟값과 같다. 새 생물에는 사용되지 않은 번호 중 가장 작은 번호가 부여된다.
그들은 주문을 사용하며, 새 생물들의 일부 특성에 관심이 있다. 이 특성들을 알아낼 수 있도록 돕는다.
첫 번째 줄에 정수 n, k, q (1 ≤ n ≤ 105, 1 ≤ k ≤ 12, 1 ≤ q ≤ 105)가 주어진다. 각각 특성, 생물, 질의의 수이다.
다음 k개의 줄은 원래 존재하는 생물들을 설명한다. i번째 줄에는 i-th 생물의 특성을 나타내는 n개의 수 ai1, ai2, ..., ain (1 ≤ aij ≤ 109)이 주어진다.
이어지는 q개의 각 줄에는 질의가 하나씩 주어진다. 이 줄들 중 i-th 줄에는 수 ti, xi, yi (1 ≤ ti ≤ 3)이 주어진다. 이들은 다음 질의를 나타낸다.
모든 생물의 번호가 유효함이 보장된다. 즉, 어떤 생물이 관련된 모든 질의보다 먼저 그 생물이 생성된다.
ti = 3인 각 질의에 대해 해당 특성을 출력한다.
2 2 4
1 2
2 1
1 1 2
2 1 2
3 3 1
3 4 2
2
1
5 3 8
1 2 3 4 5
5 1 2 3 4
4 5 1 2 3
1 1 2
1 2 3
2 4 5
3 6 1
3 6 2
3 6 3
3 6 4
3 6 5
5
2
2
3
4
첫 번째 예제에서 Sasha는 번호가 3이고 특성이 (2, 2)인 생물을 만든다. Nikita는 번호가 4이고 특성이 (1, 1)인 생물을 만든다. 그 후 그들은 생물 3의 첫 번째 특성과 생물 4의 두 번째 특성을 알아낸다.