공격 릴레이

이 문제에서 두 지점 사이의 거리는 택시 거리로 계산한다. 두 점 $(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$번째 줄에 출력한다.

답이 커질 수 있으므로 998244353으로 나눈 나머지를 출력한다.

• $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$)

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