$n$개의 칸이 한 줄로 배열되어 있습니다. $i$번째 칸은 색 $c_i$이며 값이 $v_i$인 공 하나가 들어 있습니다.
여러분은 이 칸들에서 여러 번 여행하려고 합니다. 각 여행마다 정수 $x$와 색 집합 $A = \{a_1, a_2, \cdots, a_k\}$가 주어지며 $c_x \in A$입니다. 여행은 칸 $x$에서 시작합니다. 여행 중 칸 $i$에 있다면 다음에는 칸 $(i - 1)$ 또는 $(i + 1)$로 이동할 수 있습니다. 이 $n$개의 칸 밖으로 나갈 수 없음에 유의하세요. 또한 어느 시점이든 현재 있는 칸의 색은 집합 $A$에 속해야 합니다.
칸 $i$에 있을 때 그 칸의 공을 제거하고 그 값 $v_i$를 얻는 것을 선택할 수 있습니다. 각 칸에는 공이 하나뿐이므로 각 칸에서 공을 제거하는 것은 한 번만 가능합니다.
여러분의 과제는 $q$개의 연산을 순서대로 처리하는 것입니다. 각 연산은 다음 세 유형 중 하나입니다:
- $1\ p\ x$: $c_p$를 $x$로 바꿉니다.
- $2\ p\ x$: $v_p$를 $x$로 바꿉니다.
- $3\ x\ k\ a_1\ a_2\ \ldots\ a_k$: 여행의 시작 칸 $x$와 색 집합 $A = \{a_1, a_2, \cdots, a_k\}$가 주어집니다. 이 여행을 한다고 가정하고 얻을 수 있는 총값의 최댓값을 계산하세요. 여행은 가정일 뿐이므로 공이 실제로 제거되지는 않음에 유의하세요. 즉, 모든 쿼리는 서로 독립적입니다.
입력
여러 테스트 케이스가 있습니다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $T$가 주어집니다. 각 테스트 케이스에 대해:
첫 번째 줄에는 칸의 개수와 연산의 개수를 나타내는 두 정수 $n$과 $q$가 주어집니다 ($1 \le n \le 10^5, 1 \le q \le 10^5$).
두 번째 줄에는 $n$개의 정수 $c_1, c_2, \ldots, c_n$가 주어집니다 ($1 \le c_i \le n$). $c_i$는 $i$번째 칸의 초기 색입니다.
세 번째 줄에는 $n$개의 정수 $v_1, v_2, \ldots, v_n$가 주어집니다 ($1 \le v_i \le 10^9$). $v_i$는 $i$번째 칸의 공의 초기 값입니다.
다음 $q$개의 줄 중 $i$번째 줄에는 $i$번째 연산이 주어집니다. 입력 형식은 다음과 같습니다:
- $1\ p\ x$: $1 \le p \le n$ 및 $1 \le x \le n$.
- $2\ p\ x$: $1 \le p \le n$ 및 $1 \le x \le 10^9$.
- $3\ x\ k\ a_1\ a_2\ \ldots\ a_k$: $1 \le x \le n$, $1 \le a_1 < a_2 < \ldots < a_k \le n$ 및 $c_x \in \{a_1,a_2,\cdots,a_k\}$.
모든 테스트 케이스에서 $n$의 합과 $q$의 합은 각각 $3 \times 10^5$를 넘지 않음이 보장됩니다. 또한 모든 테스트 케이스에서 $k$의 합은 $10^6$을 넘지 않습니다.
출력
유형 3의 각 연산에 대해 얻을 수 있는 총값의 최댓값을 나타내는 정수 하나를 한 줄에 출력하세요.
예제
입력 1
2 5 10 1 2 3 1 2 1 10 100 1000 10000 3 3 1 3 3 3 2 2 3 2 5 20000 2 3 200 3 3 2 1 3 3 3 3 1 2 3 1 3 4 2 1 100000 1 2 2 3 1 2 1 2 4 1 1 2 3 4 1000000 1000000 1000000 1000000 3 4 4 1 2 3 4
출력 1
100 110 1200 21211 100010 4000000