時間制限 : sec, メモリ制限 : KB
English / Japanese  

Stack

スタックはLIFO (Last In First Out)の制約に基づいて、データの中で最後に挿入されたものを先に取り出すデータ構造です。

整数を保持する$n$個のスタック$S_i$ ($i = 0, 1, ..., n-1$)に対して、以下の操作を行ってください。

  • push($t$, $x$): $S_t$ に整数$x$を挿入する。
  • top($t$): $S_t$から次に取り出される要素を報告する。ただし、$S_t$が空の場合は何もしない。
  • pop($t$): $S_t$から要素を取り出し削除する。ただし、$S_t$が空の場合は何もしない。

初期状態で、すべてのスタックは空とします。

Input

入力は以下の形式で与えられます。

$n \; q$
$query_1$
$query_2$
:
$query_q$

各クエリ$query_i$は

0 $t$ $x$

または

1 $t$

または

2 $t$

の形式で与えられます。最初の数字0, 1, 2 は操作の種類を示し、それぞれpush、top、popを表します。

Output

各top操作ごとに、整数を1行に出力してください。

Constraints

  • $1 \leq n \leq 1,000$
  • $1 \leq q \leq 200,000$
  • $-1,000,000,000 \leq x \leq 1,000,000,000$

Sample Input 1

3 9
0 0 1
0 0 2
0 0 3
0 2 4
0 2 5
1 0
1 2
2 0
1 0

Sample Output 1

3
5
2