/*#include<stdio.h>
int main() {
int n, arr[1001] = {0};
int i;
scanf("%d", &n);
for(i=0; i<n; i++) {
scanf("%d", &arr[i]);
}
for(i=n-1; i>=0; i--) {
printf("%d ", arr[i]);
}
}
*/
/*
int main() {
char str[1000];
int i,c;
//scanf("%s", str);
// only word
gets(str);
//
printf("%s", str);
}
*/
/*
int main()
{
int k, arr[101] = {0};
int i;
scanf("%d", &k);
for(i=0; i<k;i++){
scanf("%d", &arr[i]);
}
for(i=0; i<k; i++ )printf("%d\n", arr[i]);
for(i=0; i<k; i++ )printf("%d\n", arr[i]);
}
*/
/*
int main()
{
int k, arr[1001] ={0};
int n;
int i, j;
scanf("%d", &n);
for(i=0;i<n;i++)
{
scanf("%d", &arr[i]);
}
for(i=0;i<n;i++)
{
for(j=i; j<n+i; j++) {
printf("%d ", arr[j%n]);
}
printf("\n");
}
}
*/
/*
int main()
{
char str[100];
int i;
gets(str);
for(i=0; i<strlen(str); i++) {
if(str[i] != ' '){
printf("%c",str[i]);
}
}
}
*/
/*
int main()
{
int k, arr[11];
int i, a;
for(i=1;i<=10;i++){
scanf("%d",&arr[i]);
}
scanf("%d",&a);
printf("%d",arr[a]);
}
*/
/*
int main()
{
char str[100001]={0};
int i;
int a =0;
int b =0;
scanf("%s",str);
for(i=0;i<strlen(str);i++)
{
if(str[i]=='(') a++;
else if(str[i]==')') b++;
}
printf("%d %d", a, b);
return 0;
}
*/
/*
*/
/*
int main() {
char str1[1000], str2[1000];
char output[1000];
scanf("%s %s", str1, str2);
printf("%d", strcmp(str1, str2));
strcpy(output, str1);
printf("%s", output);
int a = 10;
int b = 20;
int tmp = a;
a = b;
b = temp;
}
*/
/*
int main()
{
char str[100];
char output[100];
scanf("%s", str);
strcpy(output, "love");
if(strcmp(str, output)==0){
printf("I love you.");
}
}
*/
/*
int main()
{
char str[11];
char output='t';
int i;
scanf("%s", str);
// strcpy(output, "t");
for(i=0; i<strlen(str); i++)
{
if(str[i]=='t')
{
printf("%d ", i+1);
}
}
}
*/
/*
int main()
{
char str1[21], str2[21], str3[21];
scanf("%s\n%s\n%s", str1, str2, str3);
if(str1[strlen(str1)-1] == str2[0] && str2[strlen(str2)-1] == str3[0] && str3[strlen(str3)-1] == str1[0])
{
printf("good");
}
else
{
printf("bad");
}
}
*/
/*
int main() {
int map[100][100] = {0}, i, j, k=1;
int n;
scanf("%d", &n);
for(i=0; i<n; i++) {
if(i%2==0)
for(j=0; j<n; j++) {
map[i][j] = k++;
}
else
for(j=0; j<n; j++) {
map[i][j] = k++;
}
}
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
printf("%d ", map[i][j]);
}
printf("\n");
}
}
*/
/*
int main()
{
int map[100][100] = {0}, i, j, k=1;
int n;
scanf("%d", &n);
for(i=0; i<n; i++) {
if(i%2==0)
for(j=0; j<n; j++)
{
map[i][j] = k++;
}
else
for(j=0; j<n; j++) {
map[i][j] = k++;
}
}
for(i=0; i<n; i++){
for(j=0; j<n; j++){
printf("%d ", map[j][i]);
}
printf("\n");
}
}
*/
/*
int main()
{
int map[100][100] = {0}, i, j, k=1;
int n, m;
scanf("%d %d", &n, &m);
}
*/