Write a program which reads $n$ items and sorts them. Each item has attributes $\\{value, weight, type, date, name\\}$ and they are represented by $\\{$ integer, integer, upper-case letter, integer, string $\\}$ respectively. Sort the items based on the following priorities.

1. first by value (ascending)
2. in case of a tie, by weight (ascending)
3. in case of a tie, by type (ascending in lexicographic order)
4. in case of a tie, by date (ascending)
5. in case of a tie, by name (ascending in lexicographic order)

Constraints

* $1 \leq n \leq 100,000$
* $0 \leq v_i \leq 1,000,000,000$
* $0 \leq w_i \leq 1,000,000,000$
* $t_i$ is a upper-case letter
* $0 \leq d_i \leq 2,000,000,000,000$
* $1 \leq $ size of $s_i \leq 20$
* $s_i \ne s_j$ if $(i \ne j)$

Input

The input is given in the following format.


$n$
$v_0 \; w_0 \; t_0 \; d_0 \; s_0$
$v_1 \; w_1 \; t_1 \; d_1 \; s_1$
:
$v_{n-1} \; w_{n-1} \; t_{n-1} \; d_{n-1} \; s_{n-1}$


In the first line, the number of items $n$. In the following $n$ lines, attributes of each item are given. $v_i \; w_i \; t_i \; d_i \; s_i$ represent value, weight, type, date and name of the $i$-th item respectively.

Output

Print attributes of each item in order. Print an item in a line and adjacency attributes should be separated by a single space.

Example

Input

5
105 24 C 1500000000000 white
100 23 C 1500000000000 blue
105 23 A 1480000000000 pink
110 25 B 1500000000000 black
110 20 A 1300000000000 gree


Output

100 23 C 1500000000000 blue
105 23 A 1480000000000 pink
105 24 C 1500000000000 white
110 20 A 1300000000000 gree
110 25 B 1500000000000 black
#include<iostream>
#include<tuple>
#include<algorithm>
using namespace std;

int main(){
  
  int n, v, w;
  char t;
  long long d;
  string s;
  
  cin >> n;
  tuple<int, int, char, long long, string> goods[n];
  for(int i = 0;i < n;i++){
    cin >> v >> w >> t >> d >> s;
    goods[i] = make_tuple(v, w, t, d, s);
  }
  
  sort(goods, goods + n);
  
  for(int i = 0;i < n;i++){
    tie(v, w, t, d, s) = goods[i];
    cout << v << " " << w << " " << t << " " << d << " " << s << endl;
  }
  
  return 0;
}
