/*
import java.util.*;
class IntStack extends Stack{
int ptr=0;
int max;
int[] stk;
public IntStack(int capacity) {
max = capacity;
try {
stk = new int [max];
}catch(OutOfMemoryError e) {
max=0;
}
}
public class EmptyIntStackException extends RuntimeException{
public EmptyIntStackException() {
}
}
public class OverflowIntStackException extends RuntimeException{
public OverflowIntStackException() {
}
}
public int push(int x) throws OverflowIntStackException{
if(ptr>=max)
throw new OverflowIntStackException();
return stk[ptr++]=x;
}
public int po() throws EmptyIntStackException{
if (ptr <= 0)
throw new EmptyIntStackException();
return stk[--ptr];
}
public int top() {
if(ptr==0) {
return -1;
}
return stk[ptr-1];
}
public int size() {
return ptr;
}
public int empt() {
if(ptr==0) {
return 1;
}
else {
return 0;
}
}
}
public class Main{
public Main() {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
IntStack s = new IntStack(n);
for(int i=0; i<n; i++) {
String str= scan.nextLine();
String[] arr = new String[2];
arr = str.split(" ");
if(arr[0].equals("push")) {
s.push(Integer.valueOf(arr[1]));
}else if(str.equals("pop")) {
s.po();
}else if(str.equals("empty")) {
s.empt();
}else if(str.equals("size")) {
s.size();
}else if(str.equals("top")) {
s.top();
}
}
}
public static void main(String[] args) {
new Main();
}
}
*/
/*
import java.util.*;
public class Main{
Random rd = new Random();
Scanner scan = new Scanner(System.in);
public Main() {
int n = (rd.nextInt(5)-1)%5;
int n1 =rd.nextInt(5)-1;
int n2 =(rd.nextInt(5)-1)%5;
String[] str = new String[6];
for(int i=0; i<5; i++) {
str[i] = scan.nextLine();
}
System.out.print(str[n]);
System.out.print(str[n1]);
System.out.print(str[n2]);
}
public static void main(String[] args) {
new Main();
}
}
*/
/*
interface ma{
void ma1();
}
class ma1 implements ma{
@Override
public void ma1() {
// TODO Auto-generated method stub
}
}
public class Main{
public Main() {
}
public static void main(String[] args) {
new Main();
}
}
*/
/*
import java.util.*;
interface management{
int push(int capacity);
int pop();
class OverflowIntStackException extends RuntimeException{};
class EmptyIntStackException{};
}
class choi implements management{
@Override
public int push(int capacity) {
// TODO Auto-generated method stub
return 0;
}
@Override
public int pop() {
// TODO Auto-generated method stub
return 0;
}
class OverflowIntStackException extends Runtime{
public OverflowIntStackException() {
}
}
}
public class Main{
public Main() {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt(); // 학생수
}
public static void main(String[] args) {
new Main();
}
}
*/
/*
import java.util.*;
public class Main{
public Main() {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] arr = new int [n];
String[] str= new String[n];
for(int i=0; i<n; i++) {
str[i] = scan.nextLine();
arr[i] = scan.nextInt();
}
for(int j=0; j<n; j++) {
for(int i=0; i<arr[j]; i++) {
}
}
}
public static void main(String[] args) {
new Main();
}
}
*/