The World Is a Single Handkerchief

Interview

Time limit1sMemory limit1024 MB

Summary

A walker starts at the origin heading along +x and turns 90 degrees left or right at given times; find the position after T seconds.

Level: Easy3 of 10
Topics: Implementation, Simulation, Math, Array
Solved: No attempts yet

Problem

Wearing old sneakers, under cool air and a clear sky, in warm sunlight, you walk hand in hand with this street you are meeting for the first time. Walking with a fluttering heart and no complicated thoughts makes you want to run, and running together leaves you out of breath. Even in the moment you gasp and sit down, the world is like a single sheet of handkerchief.

Junwon is having a cloud-like happy day right now, while the Cheonhajeil Coding Contest is under way, but unfortunately you have to solve a problem. Imagine that today, instead of Everland, Junwon is walking at the origin of the coordinate plane with an x-axis and a y-axis. Junwon's initial position is (0, 0), and he moves in the x-axis direction at a speed of 1 per second. That is, every second Junwon's x-coordinate increases by 1. However, Junwon occasionally changes direction. When he changes direction, he turns 90 degrees left or 90 degrees right.

Given a record of Junwon's direction changes as input, write a program that finds the coordinates where Junwon arrives after walking for T seconds.

Input

The first line gives the number of times Junwon changed direction, N, and the time Junwon walked, T, separated by a space.

The next N lines each give the time Ti of Junwon's i-th direction change and a string Si indicating whether Junwon turned left or right, separated by a space. Si is left if Junwon turned left and right if he turned right.

Output

If the coordinates where Junwon arrives after walking for T seconds are (x, y), print x and y in that order, separated by a space.

Constraints

0 ≤ N ≤ 100,000
1 ≤ T ≤ 1,000,000,000
0 ≤ Ti ≤ T
T1, ..., TN are all distinct and form an increasing sequence. That is, he does not change direction multiple times at one moment, and the input is given in chronological order.
Si = left or right

Examples2

Example 1
Input
```
0 100
```
Expected output
```
100 0
```
Example 2
Input
```
3 100
30 right
50 right
60 left
```
Expected output
```
20 -60
```