//#include <stdio.h>
//#include <stdlib.h>
/*
struct ManeuverGear
{
int id;
int gas;
};
int main(){
struct ManeuverGear device[100] = {0};
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d %d", &device[i].id, &device[i].gas);
}
for(int i = 0; i < 100; i++){
for(int j = 0; j < n; j++){
if(i+1 == device[j].id){
printf("%d %d\n", i+1, device[j].gas);
}
}
}
}
*/
//int arr[301] = {0};
//int arr2[301] = {0};
//
//
//
//int main(){
// int n, i;
//
// scanf("%d", &n);
// for(i = 1; i <= n; i++){
// scanf("%d", &arr[i]);
// }
//}
/*
#include<stdio.h>
#include<string.h>
int main() {
char arr[10000] = {0};
int i, j, n;
// scanf("%s", arr);
gets(arr);
for(i=0; i<strlen(arr); i++) {
printf("%c(%d)\n", arr[i],arr[i]);
}
printf("%s", arr);
}
*/
// strcmp <
//#include<string.h>
//
//int main(){
// char arr[10000] = {0};
//
// scanf("%s", arr);
// printf("%s", arr);
//}
//#include<string.h>
//
//int main(){
// char arr[10] = {0};
//
// scanf("%s", arr);
// printf("%s", arr);
//}
//#include<string.h>
//
//int main(){
// char arr[30] = {0};
//
// gets(arr);
// printf("%s", arr);
//}
//#include<string.h>
//
//int main(){
// char arr[100000] = {0};
//
// scanf("%s", arr);
//
// if(arr[0] == 'l' && arr[1] == 'o' && arr[2] == 'v' && arr[3] == 'e' && arr[4] == 0){
// printf("I love you.");
// }
// else{
// return;
// }
//}
//#include<string.h>
//
//int main(){
// char arr[10000] = {0};
//
// scanf("%s", arr);
// if(strcmp(arr, "love")==0){
// printf("I love you.");
// }
//
//}
//#include<stdio.h>
//
//int main(){
// char arr[20] = {0};
//
// gets(arr);
//
// for(int i = 0; i < strlen(arr); i++){
// printf("%c", arr[i]+2);
// }
// printf("\n");
// for(int i = 0; i < strlen(arr); i++){
// printf("%c", (arr[i]*7)%80+48);
// }
//}
//#include<string.h>
//
//int main(){
// char arr[101] = {0};
// int i, count=0, combi=0;
//
// scanf("%s", arr);
//
// for(i = 0; i < strlen(arr); i++){
// if(arr[i] == 'c' || arr[i] == 'C'){
// count += 1;
// }
// }
// printf("%d\n", count);
// for(i = 0; i < strlen(arr); i++){
// if((arr[i] == 'C'||arr[i] == 'c')&&(arr[i+1] == 'C'||arr[i+1] == 'c')){
// combi += 1;
// }
// }
// printf("%d", combi);
//}
//#include<string.h>
//
//int main(){
// char arr[101] = {0}, arr1[101] = {0};
// int i;
//
// scanf("%s %s", arr, arr1);
//
// if(strlen(arr) > strlen(arr1)){
// printf("%s %s", arr1, arr);
// }
// else if(strlen(arr) < strlen(arr1)){
// printf("%s %s", arr, arr1);
// }
// else
// {
// for(i = 0; i < strlen(arr); i++){
// if(arr[i] > arr1[i]){
// printf("%s %s", arr1, arr);
// break;
// }
// else if(arr[i] < arr1[i]){
// printf("%s %s", arr, arr1);
// break;
// }
// }
// }
//
//}
//#include<string.h>
//
//int main(){
// char arr[10000] = {0};
// int i, sum=0;
//
// scanf("%s", arr);
// for(i = 0; i < strlen(arr); i++){
// sum += arr[i]-'0';
// }
//
// if(sum%3 == 0){
// printf("1");
// }
// else{
// printf("0");
// }
//}
//#include<string.h>
//
//int main(){
// char arr[21] = {0}, arr1[21] = {0}, arr2[21] = {0};
//
// scanf("%s\n%s\n%s",arr, arr1, arr2);
//
// if(arr[strlen(arr)-1] == arr1[0]
// && arr1[strlen(arr1)-1] == arr2[0]
// && arr2[strlen(arr2)-1] == arr[0]){
// printf("good");
// }
// else{
// printf("bad");
// }
//}
//#include<string.h>
//
//int main(){
// char arr[101] = {0};
// int count = 0, i;
//
// gets(arr);
//
// for(i = 0; i < strlen(arr); i++){
// if(arr[i] == 'l' && arr[i+1] == 'o' &&
// arr[i+2] == 'v' && arr[i+3] == 'e'){
// count += 1;
// }
// }
// printf("%d", count);
//}
//#include <stdio.h>
//int a[10001];
//int n, i, j, temp;
//int main() {
// scanf("%d", &n);
// for (i=1; i<=n; i++)
// scanf("%d", &a[i]);
//
// for(i=1; i<n; i++)
// {
// for(j=1; j<n; j++)
// {
// if (a[j] > a[j+1])
// {
// temp = a[j];
// a[j] = a[j+1];
// a[j+1] = temp;
// }
// }
// }
//
// for (i = 1; i <= n; i++)
// printf("%d\n", a[i]);
// return 0;
//}
//#include<stdio.h>
//
//int main()
//{
// int n, i, j, temp, change = 0, num = 0;
// int a[1000] = {0};
//
// scanf("%d", &n);
// for(i = 1; i <= n; i++)
// {
// scanf("%d", &a[i]);
// }
// if(n == 2){
// printf("1");
// }
// for(i = 1; i < n; i++)
// {
// change = 0;
// num += 1;
// for(j = 1; j < n; j++)
// {
// if(a[j] > a[j+1])
// {
// temp = a[j];
// a[j] = a[j+1];
// a[j+1] = temp;
// change = 1;
// }
// }
// if(change == 0)
// {
// printf("%d", num-1);
// break;
// }
// }
//}
//#include <stdio.h>
//int a[10001];
//int n, i, j, temp, min;
//int main() {
// scanf("%d", &n);
// for (i = 1; i <= n; i++)
// scanf("%d", &a[i]);
// for (i=1; i<n; i++) {
// min=i;
// for (j=i+1; j<=n; j++) {
// if(a[j] < a[min]){
// min = j;
// }
// }
// temp = a[i];
// a[i] = a[min];
// a[min] = temp;
// }
// for (i=1; i<=n; i++)
// printf("%d\n", a[i]);
// return 0;
//}