Descripción

Se acerca la Navidad y en el pueblo ya comenzaron las tradicionales posadas. Como cada año, don Liborio reparte los tamales a los niños que hacen fila frente a su casa.

Sin embargo, los niños son muy listos: cuando un niño llega a la fila y ya hay otro niño de su MISMA ESCUELA, no se forma hasta el final, sino que se mete justo DETRÁS DEL ÚLTIMO NIÑO DE SU MISMA ESCUELA que ya esté en la fila. Pero si no hay ningún niño de su escuela en la fila, entonces sí se forma hasta el final como corresponde.

Cada niño:

• Tiene un identificador único \((ID)\).
• Pertenece a una sola \(\text{ESCUELA}\).
• Nunca entra dos veces sin haber recibido antes sus tamales.

Ya que don Liborio es tu abuelo y tú como eres programador competitivo quieres ayudarlo para solucionar esa situación, considerando la llegada de los niños y la entrega de los tamales.

Entrada

Primero se te dará un número entero \(N\) \((1 \leq N \leq 2 \cdot 10^5)\) — el número de eventos que ocurren durante la posada.

Las siguientes \(N\) líneas describen cada evento:

• \(L\), \(ID\) y \(E\) — Un niño con número de identificación \(ID\) y que pertenece a la escuela \(E\) llega a la fila para recibir sus tamales.
• \(R\) — Don Liborio entrega los tamales al niño que está hasta enfrente de la fila, y ese niño se retira.

Se garantiza que:

• Siempre que ocurra un evento \(R\), hay al menos un niño en la fila.
• Cada \(ID\) es único.

Los valores de \(ID\) pueden ser grandes \(1 \leq ID \leq 10^9\).

Los valores de la \(\text{ESCUELA}\) satisfacen: \(1 \leq E \leq 10^9\).

Salida

Por cada evento \(R\), imprime en una línea el identificador \((ID)\) del niño que recibió sus tamales.

Ejemplo

Entrada

8
L 101 1
L 201 2
L 102 1
R
L 301 3
R
R
R

Salida

101
102
201
301