Service Desk

Customers arrive at a service desk at given seconds. Each customer is either normal or urgent.

The desk processes time in whole seconds starting from second $1$. At each second, all customers whose arrival time is at most that second are considered waiting. If at least one customer is waiting, exactly one customer is served.

• On an odd second, serve the waiting customer who arrived earliest.
• On an even second, serve an urgent customer first (if any urgent customer is waiting); otherwise serve the waiting normal customer who arrived earliest.

If no customer is waiting at a second, nobody is served at that second.

Determine the order in which customers are served.

Input

The first line contains an integer $n$, the number of customers.

The next $n$ lines each contain:

• an integer $t_i$ (arrival second), and
• a character $c_i$ (U for urgent, N for normal).

Customer $i$ corresponds to line $i$ (1-indexed) in this list.

Output

Print $n$ lines. On line $k$, print the index of the customer served as the $k$-th served customer.

Constraints

• $1 \le n \le 2 \cdot 10^5$
• $1 \le t_i \le 10^9$
• all $t_i$ are pairwise distinct
• $c_i \in \{\texttt{U}, \texttt{N}\}$

Example 1

5
1 U
2 N
3 N
4 U
5 N

1
2
3
4
5

Explanation

• Each customer arrives at a different second, and the first four are served immediately.
• At second 4 (even), customer 4 is urgent and is served.
• Then customer 5 is served.

Example 2

4
2 N
4 U
5 N
7 U

1
2
3
4