#include <bits/stdc++.h>
using namespace std;
/*
//1. 1부터 N까지 M의 배수합
int main() {
int n, m, i, sum=0;
cin >> n >> m;
for(i=1; i<=n; i++){
if(i % m == 0){
sum += i;
}
}
cout << sum ;
return 0;
}
*/
/*
// 2. 자연수의 합
int main() {
int n, a, max =-2147000000 , min=2147000000, i;
cin >> n ;
for(i=1; i<=n; i++){
cin >> a;
if( a > max) max = a;
if( a < min) min = a;
}
cout << max - min;
return 0;
}
*/
/* 6. 숫자만 추출
int main(){
char a[100];
int i, res=0, cnt=0;
scanf("%s", &a);
for(i=0; a[i]!='\0'; i++){
if(a[i] >= 48 && a[i] <= 57){
res = res *10 + (a[i] - 48);
}
}
printf("%d\n", res);
for(i=1; i<=res; i++){
if(res % i == 0 ) cnt++;
}
printf("%d\n", cnt);
return 0;
}
*/
/* 7. 영어단어 복구
int main(){
//freopen("input.txt", "rt", stdin);
char a[101], b[101];
int i, p=0;
gets(a);
for(i=0; a[i]!='\0'; i++){
if(a[i]!=' '){
if(a[i]>=65 && a[i]<=90){
b[p++]=a[i]+32;
}
else b[p++]=a[i];
}
}
b[p]='\0';
printf("%s\n", b);
return 0;
}
*/
/*
//8. 올바른 괄호
int main(){
char a[100];
int i, cnt=0;
scanf("%s", &a);
for(i=0; a[i]!='\0'; i++){
if(a[i]=='(') cnt++;
else if(a[i]==')') cnt--;
if(cnt<0) break;
}
if(cnt==0) printf("YES\n");
else printf("NO\n");
return 0;
}
*/
/*
// 10. 자릿수의 합
int digit_sum(int x){
int sum=0, tmp;
while(x >0){
tmp = x % 10;
sum += tmp;
x /= 10;
}
return sum;
}
int main(){
int i, num, max = -2140000000, sum, n, res;
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d", &num);
sum=digit_sum(num);
if(sum > max) {
max = sum;
res = num;
}
else if( sum == max){
if( num > res) res = num;
}
}
printf("%d\n", res);
return 0;
}
*/
/*
int main(){
int i, n, max = -2147000000, h[101], cnt=0;
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d", &h[i]);
}
max = h[n];
for(i=n-1; i>=1; i--){
if(h[i] > max){
max = h[i];
cnt++;
}
}
printf("%d\n", cnt);
return 0;
}
*/
/*
//22. 온도의 최대값
int main(){
int n, k, i, j, sum=0, max=-2147000000;
scanf("%d %d", &n, &k);
vector<int> a(n);
for(i=0; i<n; i++){
scanf("%d", &a[i]);
}
for(i=0; i<k; i++){
sum=sum+a[i];
}
res=sum;
for(i=k; i<n; i++){
sum=sum+(a[i]-a[i-k]);
if(sum>res) res=sum;
}
printf("%d\n", max);
return 0;
}
*/
/*
//24. Jolly Jumpers
int main(){
int n, i, now, pre, pos;
scanf("%d", &n);
vector<int> ch(n);
scanf("%d", &pre);
for(i=1; i<n; i++){
scanf("%d", &now);
pos=abs(pre-now);
if(pos>0 && pos<n && ch[pos]==0) ch[pos]=1;
else{
printf("NO\n");
return 0;
}
pre=now;
}
printf("YES\n");
return 0;
}
*/
/*
//25. 석차 구하기
int main(){
//freopen("input.txt", "rt", stdin);
int i, j, a[200], b[200], n;
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d", &a[i]);
b[i]=1;
}
for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
if(a[j]>a[i]) b[i]++;
}
}
for(i=1; i<=n; i++){
printf("%d ", b[i]);
}
return 0;
}
*/
/*
//26. 마라톤
int main(){
int i, j, n, cnt=0;
scanf("%d ", &n);
vector<int> a(n+1);
for(i=1; i<=n; i++){
scanf("%d", &a[i]);
}
printf("1 ");
for(i=2; i<=n; i++){
cnt=0;
for(j=i-1; j>=1; j--){
if(a[j]>=a[i]) cnt++;
}
printf("%d ", cnt+1);
}
return 0;
}
*/
/*
//33. 3등의 성적은?
int main(){
int a[101], n, tmp, idx, i, j, cnt=0;
scanf("%d", &n);
for(i=0; i<n; i++){
scanf("%d", &a[i]);
}
for(i=0; i<n-1; i++){
for(j=i+1; j<n; j++){
if(a[i] < a[j]){
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
}
for(i=1; i<n; i++){
if(a[i] != a[i-1]) cnt++;
if(cnt ==2){
printf("%d", a[i]);
break;
}
}
return 0;
}
*/
/*
// 35. Special Sort(구글 인터뷰) 버블 정렬
int main(){
int a[101], n, tmp, min, i, j;
scanf("%d", &n);
for(i=0; i<n; i++){
scanf("%d", &a[i]);
}
for(i=0; i<n-1; i++){
for(j=0; j<n-i-1; j++){
if(a[j]>0 && a[j+1]<0){
tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
}
for(i=0; i<n; i++){
printf("%d ", a[i]);
}
return 0;
}
*/
/*
// 36. 삽입정렬
int main(){
freopen("input.txt", "rt", stdin);
int a[100], n, tmp, i, j;
scanf("%d", &n);
for(i=0; i<n; i++){
scanf("%d", &a[i]);
}
for(i=1; i<n; i++){
tmp=a[i];
for(j=i-1; j>=0; j--){
if(a[j]>tmp) a[j+1]=a[j];
else break;
}
a[j+1]=tmp;
}
for(i=0; i<n; i++){
printf("%d ", a[i]);
}
return 0;
}
*/
/*
//51. 영지(territory) 선택 : (large)
int main(){
freopen("input.txt", "rt", stdin);
int h, w, n, m, i, j, tmp, max=-2147000000;
scanf("%d %d", &h, &w);
for(i=1; i<=h; i++){
for(j=1; j<=w; j++){
scanf("%d", &a[i][j]);
dy[i][j]=dy[i-1][j]+dy[i][j-1]-dy[i-1][j-1]+a[i][j];
}
}
scanf("%d %d", &n, &m);
for(i=n; i<=h; i++){
for(j=m; j<=w; j++){
tmp=dy[i][j]-dy[i-n][j]-dy[i][j-m]+dy[i-n][j-m];
if(tmp>max) max=tmp;
}
}
printf("%d\n", max);
return 0;
}
*/
/*
//54. 올바른 괄호(stack)
int main(){
stack<char> s;
string str;
cin>>str;
for(auto x : str){
if(x=='(') s.push(x);
else{
if(s.empty() || s.top()!='('){
cout<<"NO";
return 0;
}
s.pop();
}
}
if(s.empty()) cout<<"YES";
else cout<<"NO";
return 0;
}
*/
/*
55. 기차운행(stack 응용)
int main(){
stack<int> s;
scanf("%d", &n);
vector<char> str;
for(i=1; i<=n; i++){
scanf("%d", &m);
s.push(m);
str.push_back('P');
while(1){
if(s.empty()) break;
if(j==s.top()){
s.pop();
j++;
str.push_back('O');
}
else break;
}
}
if(!s.empty()) printf("impossible\n");
else{
for(i=0; i<str.size(); i++) printf("%c", str[i]);
}
return 0;
}
*/
/*
//60. 합이 같은 부분집합(DFS : 아마존 인터뷰)
int n, a[11], total=0;
bool flag=false;
void DFS(int L, int sum){
if(sum>(total/2)) return;
if(flag==true) return;
if(L==n+1){
if(sum==(total-sum)){
flag=true;
}
}
else{
DFS(L+1, sum+a[L]);
DFS(L+1, sum);
}
}
int main(){
int i;
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d", &a[i]);
total+=a[i];
}
DFS(1, 0);
if(flag) printf("YES\n");
else printf("NO\n");
return 0;
}
*/
/*
//61. 특정 수 만들기(DFS : MS 인터뷰)
int a[11], n, m, cnt=0, path[11];
void DFS(int L, int sum){
if(L == n+1){
if(sum == m){
cnt++;
for(int i=1; i<=n; i++){
printf("%d", path[i]);
}
puts("");
}
}
else {
path[L] = a[L];
DFS(L+1, sum + a[L]);
path[L] = -a[L];
DFS(L+1, sum - a[L]);
path[L] =0;
DFS(L+1, sum);
}
}
int main(){
int i;
scanf("%d %d", &n, &m);
for(i=1; i<=n; i++){
scanf("%d", &a[i]);
}
DFS(1, 0);
if(cnt==0) printf("-1\n");
else printf("%d\n", cnt);
return 0;
}
*/
/*
//64. 경로 탐색(DFS)
int map_[30][30], ch[30], cnt=0, n, path[30];
void DFS(int v, int L){
int i,j;
if(v==n){
cnt++;
for(j=0; j<L; j++){
printf("%d ", path[j]);
}
puts("");
}
else {
for(i=1; i<=n; i++){
if(map_[v][i] == 1 && ch[i] == 0){
ch[i] = 1;
path[L]=i;
DFS(i, L+1);
ch[i]=0;
}
}
}
}
int main(){
int m, i, j , a, b,c;
scanf("%d %d", &n, &m);
for(i=1; i<=m; i++){
scanf("%d %d", &a, &b);
map_[a][b] = 1;
}
ch[1] = 1;
path[0]=1;
DFS(1,1);
printf("%d\n", cnt);
return 0;
}
*/
/*
//65. 미로탐색(DFS)
int map_[10][10], ch[10][10];
int dx[4]={1, 0, -1, 0};
int dy[4]={0, 1, 0, -1};
int cnt=0;
void DFS(int x, int y){
int xx, yy, i;
if(x==7 && y==7){
cnt++;
}
else {
for(i=0; i<4; i++){
xx = x + dx[i];
yy = y + dy[i];
if(xx <1 || xx >7 || yy <1 || yy>7) continue;
if(map_[xx][yy] == 0 && ch[xx][yy] == 0){
ch[xx][yy] = 1;
DFS(xx, yy);
ch[xx][yy] =0;
}
}
}
}
int main(){
int i, j;
for(i=1; i<=7; i++){
for(j=1; j<=7; j++){
scanf("%d", map_[i][j]);
}
}
ch[1][1] =1;
DFS(1, 1);
printf("%", cnt);
return 0;
}
*/
/*
//66. 경로 탐색(DFS : 인접리스트 방법)
int ch[30], cnt=0, n, path[30];
vector<int> map_[30];
void DFS(int v, int L){
int i, j;
if(v==n){
cnt++;
for(j=0; j<L; j++){
printf("%d ", path[j]);
}
puts("");
}
else{
for(i=0; i<map_[v].size(); i++){
if(ch[map_[v][i]]==0){
ch[map_[v][i]]=1;
path[L]=map_[v][i];
DFS(map_[v][i], L+1);
ch[map_[v][i]]=0;
}
}
}
}
int main(){
int m, i, j, a, b, c;
scanf("%d %d", &n, &m);
for(i=1; i<=m; i++){
scanf("%d %d", &a, &b);
map_[a].push_back(b);
}
ch[1]=1;
path[0]=1;
DFS(1, 1);
printf("%d\n", cnt);
return 0;
}
*/
// int : 2147000000
// 문자 '0' = 48, 문자 -> 숫자 : -48 (48 ~ 57)
// 대문자 : 65 ~ 90 , 대문자 -> 소문자 : + 32
// 소문자 : 97 ~ 122
