Walking on the Road

On an infinite road, positions are indicated by an integer \(A\). When \(A = 0\) there stands the royal palace. For \(A > 0\), the position is \(A\) meters east of the palace, and for \(A < 0\), it is \(|A|\) meters west of the palace.

There are \(N\) houses located on the road, numbered from \(1\) to \(N\) from west to east. Each house is located at an even integer coordinate, and each house is inhabited by one person. The king has ordered everyone to go for a walk. Each person walks at a speed of \(1\) meter per second, and each one has a predetermined direction: either east or west. All persons leave their respective houses simultaneously.

However, the citizens are very talkative: if two people meet while walking, they stop and start chatting, and they never resume walking. Moreover, if a moving person meets someone who has already stopped (i.e. their positions coincide), he also stops to chat immediately. After \(T\) seconds, the king wishes to know the positions of \(Q\) important persons (specified by their house numbers). Can you help him determine their positions?

Note on Collisions: Suppose a person starting at \(A\) walking east would normally reach \(A+T\) if uninterrupted, and a person walking west would reach \(A-T\). However, if an eastward-moving person and a westward-moving person meet, they will both stop at the meeting point, which is at \(\frac{A_i+A_j}{2}\) (in \(\LaTeX\) format); if a moving person would pass through such a meeting point, they instead stop at the meeting point.

inputFormat

The input is given in the following format:

N T Q
A1 D1
A2 D2
... 
AN DN
X1
X2
...
XQ

Where:

• \(N\) is the number of houses.
• \(T\) is the number of seconds after the command is given.
• \(Q\) is the number of important persons to query.
• Each of the next \(N\) lines contains an even integer \(A_i\) (the location of the \(i\)-th house) and a character \(D_i\) which is either E (east) or W (west). The houses are listed in increasing order of \(A_i\) (i.e. from west to east).
• Each of the next \(Q\) lines contains a single integer \(X\) (\(1 \le X \le N\)), representing the house number of an important person.

outputFormat

For each query, output the final position of the important person (in meters) after \(T\) seconds.

sample

3 5 3
-8 E
-4 W
2 W
1
2
3

-6
-6
-3