페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8201
서브태스크

테니스 0.5s 1024MB

문제

정올국에서 N명의 선수들을 대상으로 테니스 대회를 개최하려 한다. 이 대회의 주최자인 전골이는 자신이 베팅한 선수가 우승하도록 대회 일정과 대회 장소를 조정하고자 한다.

구체적으로, 대회 장소는 A, B, C의 세 곳이 있다. 대회의 각 경기는 이 세 장소 중 한 곳을 선택하여 진행된다.

대회는 N-1번의 경기가 순서대로 이루어지며, 각 경기에서 패배한 선수는 탈락하고, 승리한 선수는 남아있게 된다. 이 과정을 전부 거친 뒤 남아있는 한명의 선수가 우승을 하게 된다.

N명의 선수에 대해 사전에 각 경기 장소에 따른 능력치가 사전에 조사되었다. 각 경기장에 대해 1부터 N 사이의 자연수로 이루어진 길이 N의 순열 A_1, A_2, ..., A_N, B_1, B_2, ..., B_N, C_1, C_2, ..., C_N이 주어진다. 경기장이 주어졌을 때, 그 경기장에 해당하는 순열의 값이 더 작은 쪽이 항상 경기를 이김이 보장된다. 예를 들어, 3번 선수와 7번 선수가 경기장 B에서 경기를 치룬다면, B_3와 B_7 중 더 작은 값을 가진 쪽이 승리하게 된다.

하지만 이 능력치는 대회가 시작되기 전까지 유동적으로 바뀔 수도 있다. 따라서 다음의 두 종류 쿼리를 실행할 수 있는 프로그램을 만들고자 한다.

  • 1 X : X번 선수가 우승할 수 있다면 "DA", 우승할 수 없다면 "NE"를 한 줄에 출력한다. (1\leq X\leq N)

  • 2 P Y Z : P=1이라면 배열 A에 대해, P=2이라면 배열 B에 대해, P=3이라면 배열 C에 대해, Y번째 값과 Z번째 값을 서로 바꾼다. (1\leq P\leq 3, 1\leq Y\leq N, 1\leq Z\leq N, Y\neq Z)


입력

첫 줄에 N과 Q가 공백으로 주어진다. N은 선수의 수이고, Q는 쿼리의 개수이다. (1\leq N, Q\leq 100000)

그 다음 줄에 A_1, A_2, ..., A_N이 주어진다.

그 다음 줄에 B_1, B_2, ..., B_N이 주어진다.

그 다음 줄에 C_1, C_2, ..., C_N이 주어진다.

그 다음 Q개의 줄에 걸쳐 쿼리의 정보가 1 X 또는 2 P Y Z 꼴로 주어진다.


출력

1 X 종류의 쿼리에 대해, 답을 한 줄에 하나씩 출력하여라.


부분문제

번호 점수 조건
#17점

N\leq 15, Q\leq 10

#211점

N\leq 1000, Q\leq 10

#312점

Q\leq 10

#421점

모든 쿼리는 1 X 꼴이다.

#549점

추가 제한 없음


예제 #1

4 4
1 2 3 4
2 1 3 4
2 4 3 1
1 1
1 4
2 3 1 4
1 4
DA
DA
NE

예제 #2

6 7
4 6 1 5 3 2
5 1 4 2 6 3
4 6 1 5 2 3
1 2
2 2 4 5
1 1
2 2 4 5
2 2 5 6
1 2
1 1
DA
NE
NE
DA

출처

COI 2019
로그인해야 코드를 작성할 수 있어요.