좌석

$H$행 $W$열의 직사각형 강당에 좌석이 $HW$개 있습니다. 행은 0부터 $H-1$까지, 열은 0부터 $W-1$까지 번호가 매겨져 있습니다. $r$행 $c$열의 좌석은 $(r, c)$로 나타냅니다.

참가자는 $HW$명이며 0부터 $HW-1$까지 번호가 붙어 있습니다. 좌석 배치표는 참가자 $i$를 좌석 $(R_i, C_i)$에 배정하고, 각 좌석에는 참가자가 정확히 한 명씩 배정됩니다.

좌석들의 집합 $S$가 직사각형이라는 것은 다음 조건을 만족하는 정수 $r_1$, $r_2$, $c_1$, $c_2$가 존재한다는 뜻입니다.

• $0 \le r_1 \le r_2 \le H-1$
• $0 \le c_1 \le c_2 \le W-1$
• $S$는 $r_1 \le r \le r_2$이고 $c_1 \le c \le c_2$인 모든 좌석 $(r, c)$로만 이루어진다.

직사각형 좌석 집합이 $k$개의 좌석으로 이루어져 있고($1 \le k \le HW$), 그 좌석에 배정된 참가자 번호가 0부터 $k-1$까지이면 이 집합을 아름다운 집합이라고 합니다. 좌석 배치표의 아름다움은 아름다운 직사각형 좌석 집합의 개수입니다.

교체 요청은 0번부터 $Q-1$번까지 순서대로 들어옵니다. $j$번째 요청은 참가자 $A_j$와 $B_j$의 좌석을 서로 맞바꾸는 것입니다. 요청이 들어오면 바로 처리해 배치표에 반영하고, 요청을 처리할 때마다 현재 배치표의 아름다움을 구합니다.

• $1 \le H$
• $1 \le W$
• $HW \le 1{,}000{,}000$
• $0 \le R_i \le H-1$ ($0 \le i \le HW-1$)
• $0 \le C_i \le W-1$ ($0 \le i \le HW-1$)
• $(R_i, C_i) \ne (R_j, C_j)$ ($0 \le i < j \le HW-1$)
• $1 \le Q \le 50{,}000$
• swap_seats를 호출할 때마다 $0 \le a \le HW-1$
• swap_seats를 호출할 때마다 $0 \le b \le HW-1$
• swap_seats를 호출할 때마다 $a \ne b$