Polite People

Interview

Time limit1sMemory limit1024 MB

Summary

Given N people in a line and a sequence of A doors (front person moves to the back) and B doors (line reverses), print the final order.

Level: Easy3 of 10
Topics: Simulation, Queue
Solved: No attempts yet

Problem

A corridor has $N$ very polite people in a single line. The corridor has two kinds of doors.

Type A doors open by pulling. When the line reaches such a door, the first person lets everyone else go ahead in order, and then becomes the last person in line. The relative order of the other people does not change.
Type B doors open by pushing. When the line reaches such a door, the first person lets the second person go first, the second lets the third go first, and so on. After passing a type B door, the whole line is reversed: the person who was last becomes first, and the person who was first becomes last.

The polite people are initially numbered from $1$ to $N$ . You are given the sequence of doors they must pass. Find the order of the people after they have passed all the doors.

Input

The first line contains the number of polite people $N$ . The second line contains the number of doors $M$ . Each of the next $M$ lines contains one character, either A or B, which is the type of a door. The doors are listed in the order the people pass them.

Output

Print $N$ numbers, one per line. These are the numbers of the polite people in the order they are standing after passing all the doors.

Constraints

$1 \le N \le 100\,000$
$0 \le M \le 100\,000$

Examples1

Example 1
Input
```
5
4
A
A
B
A
```
Expected output
```
1
5
4
3
2
```