[코드트리] 루돌프의 반란

import sys
import heapq
input = sys.stdin.readline

dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)

def move_rudol():
    dist = []
    for sn in santa.keys():
        sr, sc, score, state = santa[sn]
        if state != 3:
            heapq.heappush(dist, (abs(rudol[0]-sr)**2 + abs(rudol[1]-sc)**2, -sr, -sc, sn))
    tmp = heapq.heappop(dist); target = tmp[3]

    x = (santa[target][0] - rudol[0]) 
    if x != 0: x //= abs(santa[target][0] - rudol[0])
    y = (santa[target][1] - rudol[1])
    if y != 0: y //= abs(santa[target][1] - rudol[1])

    board[rudol[0]][rudol[1]] = 0
    rudol[0] += x; rudol[1] += y
    if board[rudol[0]][rudol[1]] != 0: #산타가 있는 경우 -> 충돌
        crash_rudol(rudol[0], rudol[1], board[rudol[0]][rudol[1]], x, y)
    board[rudol[0]][rudol[1]] = -1

def crash_rudol(ar, ac, p, x, y):
    santa[p][2] += C
    santa[p][3] = 2
    nr = ar + C*x; nc = ac + C*y
    if 0<=nr<N and 0<=nc<N:
        if board[nr][nc] != 0: #다른 산타가 있는 경우 -> 상호작용
            interaction(board[nr][nc], nr, nc, x, y)
            board[nr][nc] = p
            santa[p][0] = nr; santa[p][1] = nc
        else:
            board[nr][nc] = p
            santa[p][0] = nr; santa[p][1] = nc
    else: #탈락
        santa[p][3] = 3

def interaction(p, r, c, x, y):
    nr = r + x; nc = c + y #밀려날 위치
    if 0<=nr<N and 0<=nc<N:
        if board[nr][nc] != 0:
            interaction(board[nr][nc], nr, nc, x, y)
            board[nr][nc] = p
            santa[p][0] = nr; santa[p][1] = nc
        else:
            board[nr][nc] = p
            santa[p][0] = nr; santa[p][1] = nc
    else:
        santa[p][3] = 3 #탈락
    
def move_santa():
    for p in range(1, P+1):
        if santa[p][3] == 0:
            sr, sc, score, state = santa[p]
            dist = []
            for i in range(4):
                nsr = sr + dx[i]; nsc = sc + dy[i]
                if 0<=nsr<N and 0<=nsc<N:
                    if board[nsr][nsc] == 0 or board[nsr][nsc] == -1:
                        cur_di = abs(rudol[0]-sr)**2 + abs(rudol[1]-sc)**2
                        new_di = abs(rudol[0]-nsr)**2 + abs(rudol[1]-nsc)**2
                        if cur_di > new_di: heapq.heappush(dist, (new_di, i)) #더 가까워지지 않으면 움직이지 않아야함!
            if dist:
                tmp = heapq.heappop(dist); i = tmp[1]
                nsr = sr + dx[i]; nsc = sc + dy[i]
                board[sr][sc] = 0
                if board[nsr][nsc] == -1: #루돌프와 충돌
                    crash_santa(nsr, nsc, p, (i+2)%4)
                else:
                    board[nsr][nsc] = p
                    santa[p][0] = nsr; santa[p][1] = nsc

def crash_santa(ar, ac, p, i):
    santa[p][2] += D
    santa[p][3] = 2
    nr = ar + D*dx[i]; nc = ac + D*dy[i]
    if 0<=nr<N and 0<=nc<N:
        if board[nr][nc] != 0: #다른 산타가 있는 경우 -> 상호작용
            interaction(board[nr][nc], nr, nc, dx[i], dy[i])
            board[nr][nc] = p
            santa[p][0] = nr; santa[p][1] = nc
        else:
            board[nr][nc] = p
            santa[p][0] = nr; santa[p][1] = nc
    else: #탈락
        santa[p][3] = 3

N, M, P, C, D = map(int, input().split())
board = [[0]*N for n in range(N)]
rudol = list(map(int, input().split())); rudol[0]-=1; rudol[1]-=1; board[rudol[0]][rudol[1]] = -1
santa = dict()
for p in range(P):
    sn, sr, sc = map(int, input().split()); sr-=1; sc-=1
    santa[sn] = [sr, sc, 0, 0] #sr, sc, score, state(0:정상, 1:기절(다음에 정상됨), 2:방금 기절, 3:탈락)
    board[sr][sc] = sn

for m in range(M):
    ##### 루돌프의 움직임
    move_rudol()
    
    ##### 산타의 움직임
    move_santa()
    
    ##### 기절 cnt 갱신
    for key in santa.keys():
        if santa[key][3] == 1 or santa[key][3] == 2: santa[key][3] -= 1

    ##### 모든 산타가 탈락한 경우 즉시 게임 종료
    cnt = 0
    for key in santa.keys():
        if santa[key][3] == 3: cnt += 1
    if cnt == P: break

    ##### 탈락하지 않은 산타들에게 1점씩 추가로 부여
    for key in santa.keys():
        if santa[key][3] != 3: santa[key][2] += 1

answer = []
for p in range(1, P+1):
    answer.append(santa[p][2])
print(" ".join(map(str, answer)))