20240518

# from collections import deque

# m, n, h = map(int, input().split())

# graph = [[list(map(int, input().split())) for in range(n)] for in range(h)]

# queue = deque()

#

# dx = [-1, 1, 0, 0, 0, 0]

# dy = [0, 0, -1, 1, 0, 0]

# dz = [0, 0, 0, 0, -1, 1]

#

# cnt = 0

# for z in range(h):

# for y in range(n):

# for x in range(m):

# if graph[z][y][x] == 1:

# queue.append((x, y, z, 0))

# elif graph[z][y][x] == 0:

# cnt += 1

#

# if cnt == 0:

# print(0)

# else:

# result = 0

#

# while queue:

# x, y, z, cnt = queue.popleft()

# result = cnt

#

# for i in range(6):

# nx = dx[i] + x

# ny = dy[i] + y

# nz = dz[i] + z

#

# if 0 <= nx < m and 0 <= ny < n and 0 <= nz < h and not graph[nz][ny][nx]:

# if graph[nz][ny][nx] == -1:

# continue

# graph[nz][ny][nx] = 1

# queue.append((nx, ny, nz, cnt + 1))

#

# for z in range(h):

# for y in range(n):

# for x in range(m):

# if graph[z][y][x] == 0:

# print(-1)

# exit()

# print(result)

# from bisect import bisect_left, bisect_right

#

# n, q = map(int, input().split())

# T = 200001

# xa = [[] for i in range(T)]

# ya = [[] for i in range(T)]

# for i in range(n):

# x, y, w = map(int, input().split())

# xa[x].append((y, w))

# ya[y].append((x, w))

#

#

# def make_list(arr, p, to):

# arr.sort()

# t = 0

# for pa, items in arr:

# p.append(pa)

# t += items

# to.append(t)

#

#

# xp = [[] for i in range(T)]

# yp = [[] for i in range(T)]

# xt = [[] for i in range(T)]

# yt = [[] for i in range(T)]

#

# for i in range(T):

# make_list(xa[i], xp[i], xt[i])

# make_list(ya[i], yp[i], yt[i])

#

#

# def get_items(p, to, left, right):

# start = bisect_left(p, left)

# end = bisect_right(p, right) - 1

#

# result = 0

# if end < start:

# result = 0

# else:

# result = to[end]

# if 0 < start:

# result -= to[start - 1]

#

# return result

#

#

# x, y, ans = 1, 1, 0

# for i in range(q):

# d, v = map(int, input().split())

# if d == 0:

# ans += get_items(yp[y], yt[y], x + 1, x + v)

# x += v

# elif d == 1:

# ans += get_items(xp[x], xt[x], y + 1, y + v)

# y += v

# elif d == 2:

# ans += get_items(yp[y], yt[y], x - v, x - 1)

# x -= v

# elif d == 3:

# ans += get_items(xp[x], xt[x], y - v, y - 1)

# y -= v

#

# print(ans)

//#include<stdio.h>

//#include<vector>

//#include<string.h>

//char str[1002];

//char str2[1002];

//int main()

//{

// int i,j;

// scanf("%s",str1);

// scanf("%s",str2);

// str1_len = strlen(str1);

// str2_len = strlen(str2);

// vector<vector<int>>LCS(str1_len, vector<int>(str1_len+1, 0));

// for(i=1;i<=str1_len;i++)

// {

// for(j=1;j<=str2_len;j++)

// {

// if(str1[i-1] == str2[j-1])

// {

// LCS[i][j] = LCS[i-1][j-1] + 1;

// }

// else

// {

// LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);

// }

// }

// }

// printf("%d",LCS[str2_len][str1_len]);

//}

//#include<stdio.h>

//#define MOD 99824353

//int f[300001];

//int inv[300001];

//void make_comb(int a)

//{

// inv[0] = 1;

// inv[1] = 1;

// f[0] = 1;

// f[1] = 1;

// for(int i=2;i<=a+2;i++)

// {

// f[i] = 1LL*f[i-1]*i%MOD;

// }

// for(int i=2;i<=a+2;i++)

// {

// inv[i] = -1LL*(MOD/i)*inv[MOD % i] % MOD;

// }

// for(int i=2;i<=a+2;i++)

// {

// inv[i] = 1LL*inv[i-1]*((inv[i] + MOD) % MOD)%MOD;

// }

//}

//int nCr(int n, int r)

//{

// return (long long)f[n] inv[r]%MODinv[n-r]%MOD;

//}

//int main()

//{

// int i,j,n;

// int sum = 0;

// scanf("%d",&n);

// make_comb(n);

// for(i = 0; i<=n; i++)

// {

// for(j = 0; j <= i; j++)

// {

// sum += (nCr(i,j)*nCr(i,j))%MOD;

// }

// }

// printf("%d",sum);

// return 0;

//}

//#include <stdio.h>

//#include <string.h>

//char s[] = "+-";

//int a[10];

//void dfs(int d, int n)

//{

// if (d == n)

// {

// int sum = 0, p = 1;

// for (int i = 1; i < n; ++i)

// {

// if (a[i] == 1)

// {

// sum += p;

// p = i + 1;

// }

// else if (a[i] == 2)

// {

// sum += p;

// p = -i - 1;

// }

// else

// {

// p *= 10;

// if (p > 0)

// {

// p += i + 1;

// }

// else

// {

// p -= i + 1;

// }

// }

// }

// sum += p;

// if (sum == 24)

// {

// putchar('1');

// for (int i = 1; i < n; ++i)

// {

// printf("%c%d", s[a[i]], i + 1);

// }

// puts("");

// }

// return;

// }

// for (int i = 0; i < 3; ++i)

// {

// a[d] = i;

// dfs(d + 1, n);

// }

//}

//int main()

//{

// int n;

// scanf("%d", &n);

// dfs(1, n);

// return 0;

//}

//a[7][2],m;

//main(i,j,n,k,s,y,t)

//{

// scanf("%d%d",&n,&k);

// for(i=0;i<n;i++)scanf("%d%d",&s,&y),a[y][s]++;

// for(i=1;i<=6;i++)for(j=0; j<2; j++)

// {

// if(a[i][j]==0)t=0;

// else if(a[i][j]%k==0)t=a[i][j]/k;

// else t=(a[i][j]/k)+1;

// m+=t;

// }

// printf("%d",m);

//}

//#include<stdio.h>

//#define min(x,y) (x) > (y) ? (y) : (x)

//int n, arr[1000100] ;

//long long R=1e18;

//int main()

//{

// int i,j;

// scanf("%d",&n);

// for(i=1; i<=n; i++)

// {

// scanf("%d",&arr[i]);

// arr[i] %= 2;

// }

// for(j=0; j<2; j++)

// {

// long long cnt = 0, a = 0;

// for(i=1; i<=n; i++)

// {

// if(arr[i] == j)

// {

// a++;

// }

// else

// {

// cnt += a;

// }

// }

// R = min(R, cnt);

// }

// printf("%lld",R);

//}

//#include <bits/stdc++.h>

//using namespace std;

//int N;

//string S;

//vector<int> V[3];

//int main()

//{

// scanf("%s",S);

// N = S.size();

// for(int i=0; i<N; i++)

// {

// V[S[i]-'A'].push_back(i);

// }

// int r = 0;

// for(int i=(int)V[1].size()-1, j=(int)V[0].size()-1; i>=0; i--)

// {

// while(j >= 0 && V[1][i] < V[0][j])

// {

// j--;

// }

// if(j >= 0)

// {

// r++;

// j--;

// V[1].pop_back();

// }

// }

// for(int i=0, j=0; i<V[1].size(); i++)

// {

// while(j < V[2].size() && V[2][j] < V[1][i])

// {

// j++;

// }

// if(j < V[2].size())

// {

// r++;

// j++;

// }

// }

// printf("%d",r);

//}