쿠나이(수리 검)은 칼과 비슷하게 생긴 닌자들이 사용하는 정교한 무기이다. 닌자들은 이 칼을 적에게 던져서 적을 공격한다.

H개의 행(row)과 W개의 열(column)의 정사각형으로 이루어진 격자에 N명의 닌자가 있다.

모든 닌자는 정사각형의 중앙에 있으며, 하나의 정사각형에 에는 단 한 명의 닌자만 있을 수 있다.

각 닌자는 쿠나이를 가지고 있으며 네 방향(위, 아래, 좌, 우) 중 한쪽 방향을 바라보고 있다. 초기(시간 0)에,

모든 닌자들은 자신들의 쿠나이를 그가 바라보고 있는 방향으 로 던진다.

모든 쿠나이는 직선방향으로 1의 속도로 나아간다.

동시에 하나보다 많은 쿠나이가 같은 장소에 도달하면, 쿠나이들은 서로 충돌하여 사라진다.

쿠나이의 크기는 너무 작아서 무시할 수 있다. 또 한, 닌자들은 매우 빨리 움직이기 때문에 쿠나이에 맞지 않는다.

쿠나이는 다른 쿠나이와 부딪히지 않는 한 속도가 줄어들지 않고 계속 같은 방향으로 움직인다.

다음의 그림에서, 화살표는 쿠나이를 나타낸다.

화살표의 방향이 쿠나이가 움직이는 방향이다.

다음의 그림에서 굵게 표시한 쿠나이는 충돌하는 것들이다.

반면에, 다음의 각 그림에서는, 굵게 표시한 화살표는 다른 굵은 화살표와 충돌하지 않는다.

두 번째와 세 번째 그림에서 얇은 화살표는 다른 굵은 화살표와 충돌한다. 충돌한 화살표는 사라지기 때문에,

이 그림들에서는 굵은 화살표가 다른 굵은 화살표와 충돌하지 않는다.

<해야 할 일> W×H 격자에서 충분한 시간이 지난 후 쿠나이가 지나간 정사각형의 수를 계산하라.

<제약조건> 1 ≤ N ≤ 100,000 닌자의 수 1 ≤ W ≤ 1,000,000,000, 1 ≤ H ≤ 1,000,000,000 격자의 크기 1 ≤ Xi ≤ W, 1≤ Yi ≤ H 닌자들의 자료

쿠나이 (Kunai) timer 3s memory 512MB

쿠나이 (Kunai) 3s 512MB