/*
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*
#include<stdio.h>
int main(){
int arr[10];
int i, k;
for(i=0; i<10; i++) {
scanf("%d", &arr[i]);
}
scanf("%d", &k);
printf("%d", arr[k-1]);
}
*/
/*
#include<stdio.h>
int main(){
int arr[50]={0};
int i,k=0;
int n;
scanf("%d", &n);
for(i=0; i<n; i++){
scanf("%d", &arr[i]);
}
for(i=1; i<=n; i++){
if(arr[i]<arr[i+1]){
printf("%d", arr[i]);
}
}
}
*/
/*
#include<stdio.h>
int main(){
int arr[100]={0};
int i,n;
scanf("%d", &n);
for(i=0; i<100 ; i++){
arr[i] = n%2;
n/=2;
if(n==0) break;
}
for( ;i>=0; i--) {
printf("%d", arr[i]);
}
}
*/
/*
#include<stdio.h>
int main(){
int arr[100000]={0};
int i,j,n,m;
scanf("%d", &n);
for(i=1; i<n; i++){
scanf("%d", &arr[i]);
}
scanf("%d", &m);
for(j=1; j<m; j++){
scanf("%d", &arr[j]);
}
if(arr[j]==arr[i]){
printf("1");
}
else{
printf("0");
}
}
*/
/*
#include<stdio.h>
int main(){
int arr[100]={0};
int i,j,n,c;
scanf("%d %d", &n, &c);
for(i=0; i<n; i++){
scanf("%d", &arr[i]);
}
for(i=0; i<c; i++){
printf("%d ", arr[i]);
}
}
*/
//
//#include<stdio.h>
//
//int main() {
// int arr[100]= {0};
// int i, n, max=-999999;
//
// scanf("%d", &n);
//
// for(i=0; i<n; i++) {
// scanf("%d", &arr[i]);
// }
//
// for(i=0; i<n; i++) {
// if(max < arr[i]) max = arr[i];
// }
// printf("%d", max);
//
//
//}
//
//
//
/*
#include<stdio.h>
int main() {
int arr[100]={0};
int i,n, max, loc;
scanf("%d", &n);
for(i=0; i<n; i++) {
scanf("%d", &arr[i]);
}
max = -999999;
for(i=0; i<n; i++) {
if(max<arr[i]) {
max =arr[i];
loc = i;
}
}
arr[loc] = -999999;
max = -999999;
for(i=0; i<n; i++) {
if(max<arr[i]) {
max =arr[i];
loc = i;
}
}
arr[loc] = -999999;
max = -999999;
for(i=0; i<n; i++) {
if(max<arr[i]) {
max =arr[i];
loc = i;
}
}
printf("%d", max);
}
*/
/*
#include<stdio.h>
int main()
{
int arr1[100000]= {0};
int arr2[100000]= {0};
int i,j,n,m;
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d", &arr1[i]);
}
scanf("%d", &m);
for(j=0; j<m; j++)
{
scanf("%d", &arr2[j]);
}
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
{
if(arr2[i] == arr1[j])
{
printf("1 ");
break;
}
}
if(j==n)
{
printf("0 ");
}
}
}
*/
/*
#include<stdio.h>
int main() {
int arr[10000001] = {0};
int i, j, n, k;
scanf("%d", &n);
for(i=0; i<n; i++) {
scanf("%d", &k);
arr[k] = 1;
}
scanf("%d", &n);
for(i=0; i<n; i++) {
scanf("%d", &k);
printf("%d ", arr[k]);
}
}
*/
/*
#include<stdio.h>
int main(){
int arr[10000]={0};
int i,n,k,min;
scanf("%d", &n);
for(i=0; i<n; i++){
scanf("%d", &arr[i]);
}
min=23;
for(i=0; i<n; i++) {
if(min>arr[i]) {
min =arr[i];
}
}
printf("%d", min);
}
*/
/*
#include<stdio.h>
int main() {
char arr[100];
int i;
//scanf("%s", arr);
gets(arr);
for(i=0; i<strlen(arr); i++) {
printf("[%c]", arr[i]);
}
printf("%s", arr);
}
*/
/*
#include<stdio.h>
int main(){
char arr[100];
scanf("%s", &arr);
printf("%s", arr);
}
*/
/*
#include<stdio.h>
int main(){
char arr[10];
scanf("%s", &arr);
printf("%s", arr);
}
*/
/*
#include<stdio.h>
int main(){
char arr[100];
int i,love;
for(i=0; i<strlen(arr); i++){
scanf("%c", &love);
}
printf("%s", "I love you.");
}
*/