27089번 - 공격 릴레이

이 문제에서 두 지점 사이의 거리는 택시 거리로 계산된다. 두 점 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 택시 거리는 $(|x_1 - x_2| + |y_1 - y_2|)$이다.

두 부원 사이의 공격은 다음을 만족한다:

• 부원 A가 부원 B를 공격하려면 A가 B를 볼 수 있어야 한다. 시야 방향은 $+x, -x, +y, -y$ 중 하나이고 시야각은 좌우 45도이다. 시야각에 걸치는 부원도 볼 수 있다고 가정한다.
• 부원 A가 부원 B를 공격할 때 공격력은 A와 B 사이의 거리와 같다.

싸이컴 부원들은 공격 릴레이라 불리는 게임을 하는 것을 즐긴다. 이 게임은 총 $K$번의 턴으로 이루어진다. 각 턴에는 지정된 술래가 있으며, 각 턴은 아래와 같이 이루어진다.

1. 술래를 볼 수 있는 싸이컴의 모든 부원들이 술래를 공격한다.
2. 술래를 제외하고 술래의 시야 안에 있는 부원 중 술래에게 가장 가까운 부원이 다음 턴의 술래가 된다. 이런 부원이 여러 명일 경우 가장 번호가 작은 플레이어가 술래가 된다. 만약 술래가 볼 수 있는 플레이어가 없는 경우, 다음 번호의 부원이 술래가 된다. ($N$번 부원의 다음 번호는 $1$번 부원이다.)

단, 첫 번째 턴의 술래는 자랑스러운 $1$번 부원인 앤디가 맡는다.

예를 들어, $K=4$이고 아래와 같이 위치하는 경우를 생각하자.

• 1번 턴에서는 부원 4가 부원 1을 공격한다. 이후 부원 3이 술래가 된다.
• 2번 턴에서는 부원 1이 부원 3을 공격한다. 이후 부원 4가 술래가 된다.
• 3번 턴에서는 부원 1과 3이 부원 4를 공격한다. 이후 부원 1이 술래가 된다.
• 4번 턴에서는 부원 4가 부원 1을 공격한다. 이후 부원 3이 술래가 된다.

게임이 전부 끝난 후 각 부원이 받은 공격량의 총합을 출력하는 프로그램을 작성하라.

첫 줄에 두 정수 $N$과 $K$가 주어진다.

둘째 줄부터 $N+1$번째 줄까지 $N$명의 좌표 정보와 시야 정보가 주어진다. 구체적으로 $i+1$번째 줄에는 $i$번째 부원의 좌표 $X_i$와 $Y_i$, 그리고 보는 방향 $S_i$가 주어진다. $S_i$는 0, 1, 2, 3 중 하나이며, 각각 $+x$, $-x$, $+y$, $-y$ 방향을 의미한다.

각 부원이 받은 공격량의 총합을 출력하라. 단, $i$번째 부원이 받은 공격량의 총합을 $i$번째 줄에 출력하라.

답이 커질 수 있으니 $998 \ 244 \ 353$으로 나눈 나머지를 출력하여라.

• $2 \le N \le 10^5$
• $1 \le K \le 10^{18}$
• $1 \le X_i \le 10^5~(1 \le i \le N)$
• $1 \le Y_i \le 10^5~(1 \le i \le N)$
• $0 \le S_i \le 3~(1 \le i \le N)$
• $(X_i, Y_i) \neq (X_j, Y_j)~(1 \le i < j \le N)$

문제 예시 이미지의 방향은 아래와 같다.