Problem: Stack is a container of elements that are inserted and deleted according to LIFO (Last In First Out).

For $n$ stack $S_i$ ($i = 0, 1, ..., n-1$), perform a sequence of the following operations.

* push($t$, $x$): Insert an integer $x$ to $S_t$.
* top($t$): Report the value which should be deleted next from $S_t$. If $S_t$ is empty, do nothing.
* pop($t$): Delete an element from $S_t$. If $S_t$ is empty, do nothing.



In the initial state, all stacks are empty.

Constraints

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

Input

The input is given in the following format.


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


Each query $query_i$ is given by


0 $t$ $x$


or


1 $t$


or


2 $t$


where the first digits 0, 1 and 2 represent push, top and pop operations respectively.

Output

For each top operation, print an integer in a line.

Example

Input

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


Output

3
5
2

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;

class Main {
	void solve () {

		int n = nextInt(), q = nextInt();
		ArrayList<ArrayDeque<Integer>> list = new ArrayList<>();
		for (int i=0; i<n; i++) {
			list.add(new ArrayDeque<Integer>());
		}
		
		for (int i=0; i<q; i++) {
			int a = nextInt(), b = nextInt();
			if (a == 0) {
				list.get(b).addFirst(nextInt());
			}
			else if (a == 1) {
				if (list.get(b).peekFirst() != null) {
					out.println(list.get(b).getFirst());
				}
				
			}
			else if (a == 2) {
				if (list.get(b).peekFirst() != null) {
				list.get(b).removeFirst();
				}
			}
		}
		
		
	}



	// <Main Method>
	public static PrintWriter out;
	public static void main(String[] args) {
		out = new PrintWriter(System.out);
		new Main().solve();
		out.flush();
	}

	// <Default Field>
	static int maxInt = Integer.MAX_VALUE, minInt = Integer.MIN_VALUE;
	static int mod = 1000000007;

	// <Default Method>
	static int max (int... ar) {Arrays.sort(ar);return ar[ar.length-1];}
	static int min (int... ar) {Arrays.sort(ar);return ar[0];}
	static int calcManhatDistance (int x1, int y1, int x2, int y2) {
		int d = Math.abs(x1-x2)+Math.abs(y1-y2);
		return d;
	}
	static double calcEuclidDistance (double x1, double y1, double x2, double y2) {
		double d = Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
		return d;
	}
	static void printCharss (char[][] ar) {
		for (int i=0; i<ar.length; i++) {
			for (int j=0; j<ar[0].length; j++) {
				out.print(ar[i][j]);
			}
			out.println();
		}
	}

	// <Fast Scanner> START -------------------------------------------------
	static InputStream in = System.in;
	static  byte[] buffer = new byte[1024];
	static int length = 0, p = 0;
	public static boolean hasNextByte () {
		if (p < length) return true;
		else {
			p = 0;
			try {length = in.read(buffer);}
			catch (Exception e) {e.printStackTrace();}
			if (length == 0) return false;
		}
		return true;
	}
	public static int readByte () {
		if (hasNextByte() == true) return buffer[p++];
		return -1;
	}
	public static boolean isPrintable (int n) {return 33<=n&&n<=126;}
	public static void skip () {
		while (hasNextByte() && !isPrintable(buffer[p])) p++;
	}
	public static boolean hasNext () {skip(); return hasNextByte();}
	public static String next () {
		if (!hasNext()) throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int temp = readByte();
		while (isPrintable(temp)) {
			sb.appendCodePoint(temp);
			temp = readByte();
		}
		return sb.toString();
	}
	public static int nextInt () {return Math.toIntExact(nextLong());}
	public static int[] nextInts (int n) {
		int[] ar = new int[n];
		for (int i=0; i<n; i++) ar[i] = nextInt();
		return ar;
	}
	public static long nextLong () {
		if (!hasNext()) throw new NoSuchElementException();
		boolean minus = false;
		int temp = readByte();
		if (temp == '-') {
			minus = true;
			temp = readByte();
		}
		if (temp<'0' || '9'<temp) throw new NumberFormatException();
		long n = 0;
		while (isPrintable(temp)) {
			if ('0'<=temp && temp<='9') {
				n *= 10;
				n += temp - '0';
			}
			temp = readByte();
		}
		return minus? -n : n;
	}
	public static char[][] nextCharss (int h, int w, boolean b) {
		//b(番兵)がtrueなら配列を余計に確保する
		char[][] ar = new char[b?h+2:h][b?w+2:h];
		for (int i=b?1:0; i<(b?h+1:h); i++) {
			String temp = next();
			for (int j=0; j<w; j++) {
				ar[i][b?j+1:j] = temp.charAt(j);
			}
		}
		return ar;
	}
	// <Fast Scanner> END ----------------------------------------------------------
}