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

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

* enqueue($t$, $x$): Insert an integer $x$ to $Q_t$.
* front($t$): Report the value which should be deleted next from $Q_t$. If $Q_t$ is empty, do nothing.
* dequeue($t$): Delete an element from $Q_t$. If $Q_t$ is empty, do nothing.



In the initial state, all queues 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 enqueue, front and dequeue operations respectively.

Output

For each front 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

1
4
2

Solution (in CPP):

Solution:
#include <iostream>
#include <cstring>

class Queue {
public:
	int* data;
	int size;
	int memory;
	int top; //先頭要素の位置
	Queue() {
		size = 0;
		memory = 1;
		top = 0;
		data = new int[memory];
	}
	void enqueue(int x) {
		size++;
		if (size > memory) {
			// メモリ拡張
			memory *= 2;
			//std::cout << "upsizing: " << memory << std::endl;
			int* tmp = new int[memory];
			memcpy(tmp, data + top, (memory / 2) * sizeof(int));
			memcpy(tmp + size - top - 1, data, top * sizeof(int));
			top = 0;
			free(data);
			data = tmp;
		}
		data[(top + size - 1) % memory] = x;
	}
	void front() {
		if (size == 0) return;
		std::cout << data[top] << std::endl;
	}
	void dequeue() {
		if (size == 0) return;
		data[top] = 0;
		size--;
		if (size * 2 <= memory && memory > 1) {
			// メモリ縮小
			memory /= 2;
			//std::cout << "down sizing: " << memory << std::endl;
			int* tmp = new int[memory];
			if (top < memory){
			    memcpy(tmp, data + top + 1, size * sizeof(int));
			}
			else {
			    memcpy(tmp, data + top + 1, (memory * 2 - top - 1) * sizeof(int));
			    memcpy(tmp + memory * 2 - top - 1, data, (size - memory * 2 + top + 1) * sizeof(int));
			}
			top = 0;
			free(data);
			data = tmp;
		}
		else {
			top = (top + 1) % memory;
		}
	}
};

int main() {
	int n, q;
	std::cin >> n >> q;
	Queue* que = new Queue[n];
	while (q--) {
		int com, t;
		std::cin >> com >> t;
		if (com == 0) {
			int x;
			std::cin >> x;
			que[t].enqueue(x);
		}
		if (com == 1) {
			que[t].front();
		}
		if (com == 2) {
			que[t].dequeue();
		}
	}
}