34000번 - 취향 변화

문제

사람들은 각자의 취향이 존재한다. 하지만, K512의 유명한 단짝 shandy5833과 dong_gas는 같은 물건에 대해 같은 취향을 가진다! 즉 dong_gas가 좋아하는 물건은 shandy5833도 좋아하고, shandy5833이 좋아하는 물건은 dong_gas 또한 좋아한다.

두 친구는 일렬로 나열된 $N$개의 물건을 나눠 가지려 한다. dong_gas는 가장 왼쪽에서 연속하게 몇 개의 물건을 가져가고, shandy5833은 남은 물건을 가져간다. 두 친구 중 한 명이 물건을 가져가지 않는 것도 가능하다. 각 사람은 가져간 물건 중에서 좋아하는 물건의 개수 $-$ 싫어하는 물건의 개수만큼의 행복도를 얻는다.

정수로 이루어진 수열 $A_1, A_2, \dots, A_N$과 $B_1, B_2, \dots, B_N$이 주어진다.

• $A_i$는 $i$번째 위치에 $A_i$번 종류의 물건이 있음을 나타낸다.
• $B_i$는 물건의 취향을 나타낸다. $B_i$가 1ドル$이면 $i$번 종류의 물건을 좋아하는 것이고, $B_i$가 0ドル$이면 $i$번 종류의 물건을 싫어하는 것이다.

다음과 같은 $Q$개의 쿼리가 주어진다.

• 1ドル ,円 i ,円 j$: $i$번째 위치의 물건을 $j$번 종류의 물건으로 바꾼다. $(1\leq i,j\leq N)$
• 2ドル ,円 i$: $i$번 종류의 물건의 취향이 뒤바뀐다. 즉 $i$번 종류의 물건이 좋아하는 물건이었다면 싫어하는 물건으로, 싫어하는 물건이었다면 좋아하는 물건으로 바뀐다. $(1\leq i \leq N)$

매 쿼리마다 두 사람의 행복도의 곱의 최댓값을 구하여라.

입력

첫째 줄에 정수 $N$과 $Q$가 공백으로 구분되어 주어진다. $(1\leq N,Q\leq 10^5)$

둘째 줄에 정수로 이루어진 수열 $A_1,A_2,\cdots,A_N$이 공백으로 구분되어 주어진다. $(1 \leq A_i \leq N)$

셋째 줄에 정수로 이루어진 수열 $B_1,B_2,\cdots,B_N$이 공백으로 구분되어 주어진다. $(0 \leq B_i \leq 1)$

넷째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 주어진다.

출력

매 쿼리마다 정답을 한 줄에 하나씩 출력한다.

제한

힌트