직사각형의 강당에서 프로그래밍 대회를 열려고 한다.

강당은 H개의 행과 W개의 열이 있는 2차원 격자칸이다.

행들은 0부터 H-1까지 번호가 붙어 있다.

열들은 0부터 W-1까지 번호가 붙어 있다.

격자에서 r번째 행, c번째 열에 있는 자리를 (r, c)로 표현한다.

초대된 참가자는 HW명이다.

참가자들은 0부터 HW-1까지 번호를 가진다.

당신은 참가자들의 초기 자리 배치를 정해서 i번 참가자를 (R_i, C_i)자리에 배치했다.

한 자리에는 한 명의 참가자가 배치되어 있다.

강당에 있는 자리들의 집합 S에 대해서 다음 조건을 만족하는 정수 r₁, r₂, c₁, c₂가 존재하면 S를 직사각형 집합이라고 한다.

- 0 ≤ r₁ ≤ r₂ ≤ H-1

- 0 ≤ c₁ ≤ c₂ ≤ W-1

- S는 r₁ ≤ r ≤ r₂와 c₁ ≤ c ≤ c₂를 만족하는 자리 (r, c)들의 집합과 정확히 같다.

k(1 ≤ k ≤ HW)개의 자리로 구성된 직사각형 집합은 다음 조건을 만족할 때 아름답다고 한다:

그 직사각형 집합에 배치된 참가자들이 정확히 0번 부터 k-1번까지의 번호를 가진다.

자리 배치의 아름다운 정도는 존재하는 모든 아름다운 직사각형 집합의 개수이다.

초기 자리 배치를 결정한 후에, 당신은 2명의 위치를 교환해 달라는 요청을 Q개 받게 된다.

정확히 말하면, 전체 Q개의 요청이 주어지고, 각 요청은 시간 순서대로 0번부터 Q-1번까지 번호가 붙어 있다.

요청들 중 j번(0 ≤ j ≤ Q-1)은 A_j번 참가자와 B_j번 참가자의 위치를 교환해 달라는 것이다.

당신은 요청을 받은 즉시 자리 교환을 수행한다.

각 자리 교환을 수행한 다음, 그 때 자리 배치의 아름다운 정도를 계산하려고 한다.

Seats timer 4초 memory 256MB

Seats 4초 256MB