You are given a rectangular billiard board, L and W be the length and width of the board respectively. Unlike other billiard boards it doesn't have any pockets. So, the balls move freely in the board. Assume that initially some balls are in the board and all of them are moving diagonally. Their velocities are same but their direction may be different. When one or more balls bounce off, their position changes but their velocities remains the same.

You are given the initial positions of the balls and their directions; your task is to find the position of the balls after K seconds. The board is placed in the 2D plane such that the boundaries are (0,0), (L, 0), (L, W) and (0, W). The positions of the balls are given as 2D coordinates and they all lie inside the board. The directions are given as one of the following {NE, SE, SW, NW}, N, E, S and W denote North, East, South and West respectively. NE means North-East so both x and y are increasing. The balls are so small that their radii can be thought to be 0. In each second, the balls advance one unit in their direction. Here one unit doesn't mean Euclidean one unit. For example, if the current position of a ball is (x,y) and its direction is NW then in the next second its position will be (x-1, y+1).

When two or more balls bounce off, they may change their directions as shown in the pictures below. You can rotate the pictures to get all possible results. Remember that the balls may bounce at non-integer points.

Fig 1: Bouncing on walls

Fig 2: Bounce result between two balls

Fig 3: Bounce result amongst 3 balls and 4 balls

Input starts with an integer T (≤ 25), denoting the number of test cases.

Each case starts with a line containing four integers L W (5 ≤ W ≤ L ≤ 10⁸), n (1 ≤ n ≤ 1000) and K (1 ≤ K ≤ 10⁸) where n denotes the number of balls in the board. Each of the next n lines contains two integers x y and a string d, where (x, y) (0 ≤ x ≤ L, 0 ≤ y ≤ W) denotes the co-ordinate of the ball and d can be one of {NE, SE, SW, NW} which denotes the direction of the ball respectively. You can safely assume that the balls are placed in different positions initially.

For each case, print the case number in a single line. Then print the position of the balls. Sort the positions first by their x co-ordinate, and order the ones which have same x coordinate by their y coordinates all in ascending order.