''' # 1931번 회의실 배정 n = int(input()) arr = [[0 for col in range (n)] for row in range (n)] brr = [[]*n]*n memory = 0 count = 0 for i in range(n): arr[i] = list(map(int, input().split(" "))) for i in range(n): for j in range(n): if arr[i][1] <= arr[j][0]: brr[i].append(arr[j][1]) for i in range(n): for j in range(n): if brr[i][j] != 0: count += 1 if memory < count: memory = count else: count = 0 count = 0 print(brr) print (memory) memory = [] count = [] n = int(input()) arr = [0,0]*n for i in range(n): arr = list(map(int, input().split(" "))) for i in range(True): for j in range(n): if arr[i][1] <= arr[j][0]: memory.append(arr[j][0]) n = int(input()) arr = [0,0]*n for i in range(n): arr = list(map(int, input().split())) arr.sort(reverse=True) brr = [0, [0,0]]*n for i in range(n): brr[i, arr[i]] arr = input().split(" ") m = arr[0].replace('5','6') n = arr[1].replace('5','6') max1 = int(m)+int(n) m1 = arr[0].replace('6','5') n1 = arr[1].replace('6','5') min1 = int(m1)+int(n1) print(min1, max1) T = int(input()) c = [0]*T q = 0 d = 0 n = 0 p = 0 for i in range(T): c = int(input()) while(c!=0): if c>=25: c-=25 q+=1 elif c>=10 and c<25: c -= 10 d += 1 elif c<10 and c>=5: c -= 5 n += 1 else: c -= 1 p += 1 print(q,d,n,p) q,d,n,p = 0 T = int(input()) q=0 d=0 n=0 p=0 for i in range(T): c = int(input()) while(c!=0): if c>=25: q = c//25 c = c%25 elif c>=10 and c<25: d = c//10 c = c%10 elif c<10 and c>=5: n = c//5 c = c%5 else: p = c c -= p print(q,d,n,p) q=0 d=0 n=0 p=0 n = int(input()) tree = list(map(int, input().split(" "))) tree.sort(reverse=True) print(tree[0]+) ''' n = int(input()) arr = [[0 for col in range (n)] for row in range (n)] for i in range (n): arr[i] = list(map(int, input().split(" "))) crnt = 0 d = [] d = arr[0][0] for i in range(n): if d[crnt]>arr[0][i]: d[crnt] += arr[0][i] else:

''' n = int(input()) res = [] class stk: data = [] cnt = 0 def __init__(self): print("") def __init__(self, data): self.data = data def excute(self): for i in range(len(self.data)): if self.data[i] == "(": self.input() else: self.output() if self.cnt < 0: return 'NO' if self.cnt!=0: return 'NO' else: return 'YES' def input(self): self.cnt += 1 def output(self): self.cnt -= 1 for i in range(n): v = input() x = stk(v) res.append(x.excute()) for i in range(len(res)): print(res[i]) ''' ''' class stk: data = [] data1 = list(data) c = 0 cnt = 0 pnt = 0 def __init__(self): print def __init__(self, data): self.data = data self.data1 = list(data) def excute(self): for i in range(len(self.data)): if self.data[i] == '(': self.input() self.data1[self.c] = '(' self.c += 1 elif self.data[i] == '[': self.input1() self.data1[self.c] = '[' self.c += 1 elif self.data[i] == ')': self.output() if self.data1[self.c] != '(' or self.cnt<0: return 'NO' elif self.data1[self.c]=='(': self.c -= 1 elif self.data[i] == ']': self.output1() if self.data1[self.c] != '[' or self.pnt<0: return 'NO' elif self.data1[self.c]=='[': self.c -= 1 if self.cnt == 0 and self.pnt==0: return 'YES' else: return 'NO' def input(self): self.cnt += 1 def output(self): self.cnt -= 1 def input1(self): self.pnt += 1 def output1(self): self.pnt -= 1 res = [] while(True): v = input() if v =='.': break x = stk(v) res.append(x.excute()) for i in range(len(res)): print(res[i]) ''' res = [] while(True): v = input() if v == '.': break stk = [] cnt = 0 sta = True for i in v : if i == '[' or i == '(': stk.append(i) cnt += 1 elif i == ']': if stk != '[' or cnt == 0: sta = False break cnt -= 1 stk.pop() elif i == ')': if stk != '(' or cnt == 0: sta = False break cnt -= 1 stk.pop() if sta == True: print("yes") else: print("no")

''' a,b = input().split() a = int(a) b = int(b) s = 0 for i in range(a, b+1): if i%2==0: s -= i else: s += i print(s) ''' ''' a, b = input().split() a = int(a) b = int(b) s = 0 for i in range(a, b+1): if i%2==0: print('-', i, end='', sep='') s -= i else: print('+', i, end='', sep='') s += i print('=',s, sep='') ''' ''' a, b = input().split() a = int(a) b = int(b) s = 0 for i in range(a, b+1): if i%2==0: print('-', i, end='', sep='') s -= i else: if i!=a: print('+',end='') print(i, end='', sep='') s += i print('=',s, sep='') ''' ''' a,d,n = input().split() a = int(a) d = int(d) n = int(n) for i in range(n-1): a += d print(a) ''' ''' a, r, n = input().split() a = int(a) r = int(r) n = int(n) for i in range(n-1): a *= r print(a) ''' ''' a, m, d, n = input().split() a = int(a) m = int(m) d = int(d) n = int(n) for i in range(n-1): a = a * m + d print(a) ''' ''' for i in range(0, 5): # 0 ~ 4(inclusive, exclusive) for j in range(0, 5): print('*(', i, j,')' , end='') print() # location(i, j) ''' ''' n = int(input()) for i in range(n): for j in range(n): if i==0 or j==0 or i==n-1 or j==n-1: # rule print('*', end='') else: print(' ', end='') print() ''' n = input() n = int(n) for i in range(n): for j in range(n): if i==0 or j==0 or i==n-1 or j==n-1 or i==j or i+j==n-1 : # add 2 more rules print('*', end='') else: print(' ', end='') print()

''' memo = [0] memo = [memo * 10000]*100 def pas(x, y): global memo if x == 0 or y == 0: memo[x][y] = 1 else: memo[x][y] = memo[x - 1][y] + memo[x][y - 1] return print(memo[x][y]) def rec(r, c, x, y): global memo if x == 0 and y == 0: pas(x,y) x = x +1 return rec(r,c,x,y) if x == r-1 and y == c-1: return memo[x][y]%100000000 if x != r-1: pas(x,y) x = x+1 return rec(r,c,x,y) else: pas(x,y) x = 1 y = y+1 return rec(r,c,x,y) r, c = input().split() x = 0 y = 0 x = int(x) y = int(y) r = int(r) c = int(c) print(rec(r, c, x, y)) for i in range(r): for j in range(c): print(memo[i][j], end='') print("\t") memo=[0] memo = memo*100 memo = [memo]*100 def pak(x, y): global memo if x == 1 or y == 1: memo[x][y] = 1 return memo[x][y] if memo[x][y] != 0: return memo[x][y] memo[x][y] = pak(x-1, y)%100000000 + pak(x, y-1)%100000000 return memo[x][y]%100000000 def pas(r,c,x,y): global memo if y != c: if x == 0: memo[x][y]=1 y = y+1 return pas(r,c,x,y) else: if y != 0: memo[x][y]=memo[x-1][y]+memo[x][y-1] y = y+1 return pas(r,c,x,y) else: memo[x][y]=1 y = y+1 return pas(r,c,x,y) else : x = x+1 y = 0 return pas(r,c,x,y) if x==r and y==c: return memo[x][y] r,c = input().split() x = 0 y = 0 x = int(x) y = int(y) r = int(r) c = int(c) print(pak(r, c)) #print(pas(r,c,x,y)) ''' a,b = input().split() a = int(a) b = int(b) x = 0 x = int(x) d = a memo = [0]*1000 memo1 = 0 memo1 = int(memo1) def col(n,x): global memo if n == 1: memo[x]=memo[x]+1 return memo[x] if n % 2 == 0: memo[x]=memo[x]+1 return col(n/2,x) else: memo[x]=memo[x]+1 return col(3*n+1,x) def cur(a,b): global memo global memo1 global x global d if a != b: col(a,x) if memo1<=memo[x]: memo1=memo[x] x = x + 1 a = a + 1 return cur(a,b) else: for i in range(b-1): if memo[i] == memo1: return print(d+i, memo[i]) cur(a,b)

memo = [0] memo = memo*10000 def pas(x,y): global memo if x != 1 and y!=1: memo[x][y]=memo[x-1][y]+memo[x][y-1] else: memo[x][y]=1 return memo[x][y] def rec(r,c,x,y): global memo if y!=c and x!=r: if x!=r: x = x+1 pas(x,y) return rec(r,c,x,y) else: y = y+1 pas(x,y) return(r,c,x,y) else: return memo[x][y] r,c = input().split() x = 0 y = 0 x = int(x) y = int(y) r = int(r) c = int(c) print(rec(r,c,x,y))

#print("'"+"Hello"+"'") #print("\"!@#$%^&*()\'") ''' n = int(input()) print(n) print("print(\"Hello"+"\\"+"nWorld\")") a = input() b = input() a = int(a) b = int(b) print (a) print (b) a = float(input()) for i in range(3): print(a) a,b = input().split(":") a = int(a) b = int(b) print(a,b,sep=':') a,b = input().split("-") print(a+b) a = input() print(a[0:2],a[2:4],a[4:6],sep=" ") a,b = input().split(" ") a = int(a) b = int(b) print(a-b) a,b = input().split(" ") b = int(b) print(a*b) a,b =input().split(" ") a = int(a) b = int(b) print(a//b) a = float(input()) print(format(a, ".2f")) a,b = input().split(" ") a = int(a) b = int(b) print(a+b) print(a-b) print(a*b) print(a//b) print(a%b) print(format((a/b),".2f")) a,b = input().split(" ") a = int(a) b = int(b) if a<=b: print(True) else: print(False) n = int(input()) if n==0: print(False) else: print(True) a,b = input().split(" ") a = bool(int(a)) b = bool(int(b)) if a==False and a == b: print(True) else: print(False) a,b = input().split(" ") a = int(a) b = int(b) print(a ^ b) a,b,c = input().split(" ") a = int(a) b = int(b) c = int(c) arr = [a, b, c] arr.sort() print(arr[0]) a,b,c = input().split(" ") a = int(a) b = int(b) c = int(c) if a%2==0: print("even") else : print("odd") if b%2==0: print("even") else : print("odd") if c%2==0: print("even") else : print("odd") n = int(input()) if n>=90: print('A') else: if n>=70: print('B') else: if n>=40: print('C') else: print('D') n = int(input()) if n==12 or n==1 or n==2: print("winter") else: if n>=3 and n<=5: print("spring") else: if n>=6 and n<=8: print("summer") else: print("fall") n = int(input()) while n!=0: print(n) n=n-1 n = int(input()) for i in range(0,n+1): print(i) n = input() while True: if n=='q': print(n) break else: print(n) n = input() a,b = input().split(" ") a = int(a) b = int(b) for i in range(1,a+1): for j in range(1,b+1): print(i,j) n = int(input()) for i in range(1,n+1): if i%10 != 3 and i%10 != 6 and i%10 != 9: print(i,end=' ') else: print('X',end=' ') h,b,c,s = input().split(" ") h = int(h) b = int(b) c = int(c) s = int(s) k =h*b*c*s/8/1024/1024 print(format(k,".1f")+" MB") n = int(input()) k = int(1) s = int(0) while s<n: s=s+k k=k+1 print(s) a,m,d,n = input().split(" ") a = int(a) n = int(n) m = int(m) d = int(d) for i in range(0,n-1): a = a*m+d print(a) n = int(input()) a = input().split() d = [] for i in range(n): a[i]=int(a[i]) for i in range(24): d.append(0) for i in range(n): d[a[i]] += 1 for i in range(1,24): print(d[i],end=' ') n = int(input()) a = input().split() for i in range(n): a[i]= int(a[i]) a.sort() print(a[0]) d=[] for i in range (19): for j in range(19): d[i][j]=int(input()) n = int(input()) a = input().split() b = input().split() for i in range(2): a[i] = int(a[i]) b[i] = int(b[i]) for i in range(19): if d[a[0]][i]==1: d[a[0]][i]=0 else: d[a[0]][i]=1 for i in range(19): if d[i][a[1]]==1: d[i][a[1]]=0 else: d[i][a[1]]==1 for i in range(19): if d[b[0]][i]==1: d[b[0]][i]=0 else: d[b[0]][i]=1 for i in range(19): if d[i][b[1]]==1: d[i][b[1]]=0 else: d[i][b[1]]==1 for i in range(19): for j in range(19): print(d[i][j],end=" ") print("\n") a,b = input().split() a = int(a) b = int(b) n = int(input()) x = int(0) y = int(0) d = [] k = [] for i in range(a): for j in range(b): d[i][j]=0 for i in range(n): for j in range(4): k[i][j]=input() for i in range(n): for j in range(4): k[i][j]=int(k[i][j]) for i in range(n): if k[i][1]==0: for j in range(k[i][0]): x = k[i][2]-1 y = k[i][3]-1 d[x+i][y]=1 else: for j in range(k[i][0]): x = k[i][2]-1 y = k[i][3]-1 d[x][y+i]=1 for i in range(a): for j in range(b): print(d[i][j]) '''

''' n=1 while n!=0: n = int(input()) if n!= 0: print(n) n=int(input()) while n!=0: print(n-1) n = n-1 n = int(input()) k = 0 while k != n+1 : print(k) k = k+1 ''' ''' a = input() print(a) for i in range(len(a)): print(a[i]) # array not list ''' ''' arr = [] arr.append(10) print(arr) arr.append(20) print(arr) arr.append('HELLO') print(arr) for i in range(len(arr)): print(arr[i]) for i in range(len(arr[2])): print(arr[2][i]) tu = (1,2,3,4,5) print(tu) n = int(input()) sum = 0 for i in range(1, n+1): if i % 2 == 0: sum += i print(sum) n = int(input()) s=0 for i in range(1, n+1): if s >= n: break else: s += i print(i-1) ''' ''' n = int(input(), 16) for i in range(1,16): print('%X' %n, '*', '%X' %(i), '=', '%X' %(n*i), sep='') r,g,b = input().split(" ") r = int(r) g = int(g) b = int(b) for i in range(0,r): for j in range(0,g): for k in range(0,b): print(i,j,k) print (r*g*b) w,h,b = input().split(" ") w = int(w) h = int(h) b = int(b) k = w*h*b/8/1024/1024 print(format(k, '.2f'),"MB") n = int(input()) k=0 arr = [] for i in range(1, n+1): if i%3 == 0: continue print(i,end=' ') a,r,n = input().split(" ") a = int(a) r = int(r) n = int(n) for i in range(1,n): a=a*r print(a) a,b,c = input().split(" ") a = int(a) b = int(b) c = int(c) d=1 while d%a!=0 or d%b!=0 or d%c!=0: d=d+1 print(d) n = int(input()) arr = [n] arr = input().split() for i in range(n-1, -1, -1): print(arr[i], end=' ') ''' ''' n = int(input()) arr = [n] brr = [n] for i in range(1,n): k,r = input().split() k = int[k] r = int[r] arr[i]=k brr[i]=r q=1 p=1 for i in range(1,n): for j in range(1,n): if i==arr[q] and j==brr[p+1]: print(1) q=q+1 p=p+1 else : print(0) n = int(input()) data = [] for i in range(19): v = [0] v = v*19 data.append(v) for i in range(n): v = input().split() v[0] = int(v[0])-1 v[1] = int(v[1])-1 data[v[0]][v[1]] = 1 for i in range(19): for j in range(19): print(data[i][j], end =' ') print() ''' w,h = input().split() n = int(input()) w = int(w) h = int(h) data = [] for i in range(w): v = [0] v = v*h data.append(v) for i in range(n): v = input.split() v[0] = int(v[0]) - 1 v[1] = int(v[1]) - 1 v[2] = int(v[2]) - 1 v[3] = int(v[3]) - 1 if v[1]==0: data[v[2]+v[0]][v[3]]=1 else : data[v[2]][v[3]+v[0]]=1 for i in range(5): for j in range(5): print(data[i][j], end=' ') print()

a, b = input().split() a = int(a) b = int(b) print(a+b) ''' # 10 # 20 ''' a = int(input()) b = int(input()) print(a+b) ''' ''' a = ord(input()) a = a+1 print(chr(a)) ''' ''' a = int(input()) b = int(input()) print(a+b) ''' # ~6024 ''' print("Hello") print("World") print('"'+"Hello World"+'"') print('"'+"C:\Download"+"\\"+"'"+"hello"+"'"+".py"+'"') ''' #c=input() #print(c) #f= float(input()) #print(f) ''' a = input() b = input() print(b+"\n"+a) a,b = input().split() print(a+"\n"+b) s = input() print(s, s, s) y,m,d = input().split('.') print(d+'-'+m+'-'+y) ''' ''' s=input() print(s[0]) print(s[1]) print(s[2]) print(s[3]) print(s[4]) s = input().split(':') print(s[1]) ''' # + - * / % // ''' a, b = input().split() a = int(a) b = int(b) print(a//b) ''' # > >= < <= != == # and or not ''' a, b, c = input().split() a = (int(a)) b = (int(b)) c = int(c) print(a-b if a>b else b-a) a = ord(input()) print(chr(a+1)) f1, f2 = input().split() m = float(f1)*float(f2) print(m) n = input() m = input() print(int(n)*m) ''' ''' f1, f2 = input().split() print(float(f1)**float(f2)) a,b = input().split(' ') print(int(a)%int(b)) a,b = input().split(' ') k=float(a)/float(b) print(format(k, '.3f')) a,b,c = input().split(' ') sum = int(a)+int(b)+int(c) avg = float(sum/3) print(sum,format(avg,'.2f')) a,b = input().split(' ') print(int(a)*(2**int(b))) a,b = input().split(' ') print(False if int(a)==int(b) else True) a = bool(int(input())) print(not a) ''' ''' a,b = input().split(' ') a = bool(int (a)) b = bool(int (b)) print(True if a == True or b == True else False) a,b = input().split(' ') a = bool(int(a)) b = bool(int(b)) print(True if a==b else False) ''' ''' a,b,c = input().split(" ") a = int(a) b = int(b) c = int(c) if a%2==0 : print(a) if b%2==0 : print(b) if c%2==0 : print(c) a = input() a = int(a) if a<0: if a%2 == 0: print('A') else : print('B') else : if a%2 == 0: print('C') else : print('D') a = input() if a>='A' and a<='D': if a == 'A': print("best!!!") if a == 'B': print("good!!") if a == 'C': print("run!") if a == 'D': print("slowly~") else : print("what?") '''

/* import java.util.*; class Solution { public int[] solution(int[] progresses, int[] speeds) { int[] answer = {}; return answer; } } public class Main { public Main() { Scanner s = new Scanner(System.in); int[] x = new int[100]; int[] y = new int[100]; int[] count = new int[100]; for(int i=0; i<100; i++) { x[i] = s.nextInt(); } for(int i=0; i<100; i++) { y[i] = s.nextInt(); } for(int i=0; i<100; i++) { while(x[i]==100) { x[i] += y[i]; count[i] ++; } } } public static void main(String[] args) { new Main(); } } */ /* import java.util.*; class stack{ int top; int [] stack; int size; int count = 0; private int x; public stack(int size) { this.size = size; stack = new int[size]; top = -1; } public void push(int x) { stack[++top] = x; } public void pop() { stack[top--] = 0; } public void compare() { int ptr =0; int k=0; int i=ptr; while(ptr<top) { while(stack[ptr]<=stack[i]) { count ++; i++; if(stack[ptr]>stack[i]||i==top) { stack[k]=count; k++; System.out.print(count); break; } } count = 0; ptr ++; i=ptr; } System.out.print(0); } } public class Main{ public Main() { Scanner x = new Scanner(System.in); String str = x.nextLine(); int [] answer = {}; String[] str1 = new String[str.length()]; str1 = str.split(","); stack s = new stack(10000); answer = s.stack; for(int i=0; i<str1.length; i++) { s.push(Integer.valueOf(str1[i])); } s.compare(); System.out.print(answer); } public static void main(String[] args) { new Main(); } } */ /* import java.util.*; class stack{ int[] stk; int ptr; int capacity; int length; int limit; public stack(int max, int length, int weight) { capacity = max; ptr = 0; stk = new int[max]; this.length = length; this.limit = weight; // 다리가 버틸 수 있는 무게 } public void push(int x) { stk[ptr++]=x; stack1 stk1 = new stack1(length,limit); while(ptr>=0) { stk1.push(stk[ptr-1]); } this.pop(); } public void pop() { stk[--ptr]=0; } public class Main{ public Main() { Scanner s = new Scanner(System.in); int weights = s.nextInt(); // 트럭별 무게 int length = s.nextInt(); // 다리를 건널 수 있는 트럭의 개수 int weight = s.nextInt();// 다리가 버틸 수 있는 무게 stack stk = new stack(weights,length,weight); int [] x = new int[weights]; for(int i=weights-1; i>=0; i--) { x[i] = s.nextInt(); stk.push(x[i]); } } public static void main(String[] args) { new Main(); } }*/ /* import java.util.*; public class Main { public Main() { Scanner s = new Scanner(System.in); int weights = s.nextInt(); // 트럭별 무게 int length = s.nextInt(); // 다리를 건널 수 있는 트럭의 개수 int weight = s.nextInt();// 다리가 버틸 수 있는 무게 stack stk = new stack(weights,length,weight); int [] x = new int[weights]; for(int i=weights-1; i>=0; i--) { x[i] = s.nextInt(); stk.push(x[i]); } } public static void main(String[] args) { new Main(); } } class stack{ int[] stk; int ptr,capacity,limit,length; public stack(int max, int length, int weight) { this.capacity = max; this.limit = weight; this.length = length; ptr = 0; stk = new int[max]; } public void push(int x) { if(ptr==0) stk[ptr++]=x; else { int sum=0; for(int i=0; i<ptr; i++) { sum+=stk[i]; } if(limit-sum>=x) { stk[ptr+1]=stk[ptr]; stk[ptr++]=x; sum=0; }else { this.pop(); sum=0; for(int i=0; i<ptr; i++) { sum+=stk[i]; } } } } public void pop() { stk[--ptr]=0; } } */ import java.util.*; class queue{ int [] q; int [] a; int answer=0, all=0; int front, rear, capacity; public queue(int max) { this.capacity = max; q = new int[capacity]; front=0; rear=0; } public void enqueue(int x) { if(rear == 0) { q[rear++]=x; answer ++; } else{ int sum=0; for(int i=0; i<capacity; i++) { sum += q[i]; } if(capacity-sum>=x) { q[rear++]=x; answer ++; }else{ q[rear++]=0; this.enqueue(x); answer ++; } if(rear == front) { this.deque(); all += answer; answer = 0; } } } public void deque() { if(front==0) { q[++front]=0; }else { if(front == capacity) { front = 0; } } } } public class Main{ public Main() { Scanner s = new Scanner(System.in); int a = s.nextInt(); queue q = new queue(a); // 다리의 길이 int k= s.nextInt(); // 트럭 개수 int[] x = new int[k]; //트럭 for(int i=0; i<k; i++) { x[i] = s.nextInt(); q.enqueue(x[i]); } } public static void main(String[] args) { new Main(); } }

/* import java.util.*; class Solution { public int[] solution(int[] progresses, int[] speeds) { int[] answer = {}; return answer; } } public class Main { public Main() { Scanner s = new Scanner(System.in); int[] x = new int[100]; int[] y = new int[100]; int[] count = new int[100]; for(int i=0; i<100; i++) { x[i] = s.nextInt(); } for(int i=0; i<100; i++) { y[i] = s.nextInt(); } for(int i=0; i<100; i++) { while(x[i]==100) { x[i] += y[i]; count[i] ++; } } } public static void main(String[] args) { new Main(); } } */ import java.util.*; class stack{ int top; int [] stack; int size; int [] count1; int count = 0; private int x; public stack(int size) { this.size = size; stack = new int[size]; top = -1; } public void push(int x) { stack[++top] = x; } public void pop() { stack[top--] = 0; } public void compare() { int ptr =0; int k=0; int i=ptr; while(ptr<top) { while(stack[ptr]<=stack[i]) { count ++; i++; if(stack[ptr]>stack[i]||i==top) { count1[k]=count; k++; System.out.print(count); break; } } count = 0; ptr ++; i=ptr; } System.out.print(0); } } public class Main{ public Main() { Scanner x = new Scanner(System.in); String str = x.nextLine(); int [] answer = {}; String[] str1 = new String[str.length()]; str1 = str.split(","); stack s = new stack(10000); answer = s.count1; for(int i=0; i<str1.length; i++) { s.push(Integer.valueOf(str1[i])); } s.compare(); System.out.print(answer); } public static void main(String[] args) { new Main(); } }

/* import java.util.*; class dbLinkedList{ class Node<E>{ private E data; private Node<E> header; private Node<E> tail; private Node<E> prev; private Node<E> next; private Node<E> crnt; public Node() { header.next = tail; tail = null; crnt = header; } public void add(int x) { Node v = new Node<E>(); v.data = x; v.prev = crnt; v.next = crnt.next; crnt = v; } } MemoryManager manager = new MemoryManager(1000); manager.malloc(500); } class MemoryManager { private int capacity; public MemoryManager(int x) { this.capacity = x; } public class Node<E>{ private Node<E> data; private Node<E> next; private Node<E> prev; private Node<E> crnt; private Node<E> header; private Node<E> tail; public Node(){ header.next = tail; header.prev = null; tail = null; crnt = header; } } } // Node 구조 (item, prev, next) public class Main{ public Main() { } public static void main(String[] args) { new Main(); } } */ /* class GCTimeCheck{ public void time(){ long startTime = System.nanoTime(); long endTime = System.nanoTime(); System.out.println(endTime - startTime + "ns"); } } */ /* import java.util.*; public class Main{ public Main() { Scanner scan = new Scanner(System.in); } public static void main(String[] args) { new Main(); } } */ /* import java.util.*; class factorial{ private int sum = 1; private int x = 0; public factorial(int x) { this.x= x; } public void fac() { if(x!=1) { sum *= x; x--; this.fac(); } else { System.out.println(sum); } } } public class Main{ public Main() { Scanner s = new Scanner(System.in); int x = s.nextInt(); factorial f = new factorial(x); f.fac(); } public static void main(String[] args) { new Main(); } } */ /* import java.util.*; class c{ private int x, y; private int z=1; public c(int x, int y) { this.x=x; this.y=y; } public void k(){ if(x%z==0&&y%z==0&&z!=1) { System.out.println(z); }else { z++; } } } public class Main{ public Main() { Scanner s = new Scanner(System.in); int x = s.nextInt(); int y = s.nextInt(); c c = new c(x,y); c.k(); } public static void main(String[] args) { new Main(); } } */ /* import java.util.*; class hanoi{ private int x; private int y; private int z; public hanoi(int x, int y, int z){ this.x=x; // this.y=y; this.z=z; } public void move() { } } public class Main{ public Main() { Scanner s= new Scanner(System.in); int x = s.nextInt(); } public static void main(String[] args) { new Main(); } } */ /* import java.util.*; public class Main{ public Main() { int ptr=0; int count= 0; Scanner s = new Scanner(System.in); int n = s.nextInt(); int[] arr = new int[n]; for(int i=0; i<n; i++) { int k = s.nextInt(); if(k==0&&i!=0) { count++; }else{ if(k==0) count ++; arr[ptr++] = k; } } for(int i=0; i<count; i++) { System.out.println(arr[i]); } } public static void main(String[] args) { new Main(); } } */ import java.util.*; class hanoi{ private int x=1; private int y=0; private int z; public hanoi(int x, int y, int z){ this.x = x; this.y= y; this.z= z; } public void move(int y, int z) { z=y-1; if(z<0) { System.out.println(y+" to "+z); z=2; this.move(y,z); }else { System.out.println(y+" to "+z); this.move(y, z); } } } public class Main{ public Main() { Scanner s = new Scanner(System.in); int n = s.nextInt(); //원반 개수 hanoi h = new hanoi(n,n,n); h.move(); } public static void main(String[] args) { new Main(); } }

/* import java.util.*; class LinkedList<E>{ class Node<E>{ private E data; private Node<E> next; private int y; public Node(E data, Node<E> next) { this.data = data; this.next =next; } } private Node<E> head; private Node<E> crnt; private Node tail; public void add(char x) { Node v = new Node(x,null); v.data = x; v.next = tail; head.next = v; crnt.next = v; } public void middlefind() { } } public LinkedList(){ head.next = tail; crnt.next = tail; tail = null; } } public class Main{ public Main() { Scanner s = new Scanner(System.in); String str = s.nextLine(); LinkedList li = new LinkedList(); char[] chr = new char[str.length()]; for(int i=0; i<str.length(); i++) { chr[i] = str.charAt(i); li.add(chr[i]); } } public static void main(String[] args) { new Main(); } } */ /* import java.util.*; class Tree{ class Node<K,V>{ K key; V data; Node<K, V> left; Node<K, V> right; public Node(K key, V data, Node<K,V> left, Node<K,V> right) { this.key = key; this.data =data; this.left = left; this.right = right; } K getKey() { return key; } V getValue() { return data; } void print() { System.out.println(data); } private Node<K,V> root; private Comparator<? super K> comparator = null; } public class Main{ public Main() { } public static void main(String[] args) { new Main(); } } */ // //import java.util.*; // //public class Main{ // public Main() { // int k=0; // int count=0; // Scanner s = new Scanner(System.in); // String str =s.nextLine(); // // for(int i=0; i<) // // } // public static void main(String[] args) { // new Main(); // } //} //void find(int x) { // find(x*2); // find(x*2+1); // print(x); //} // //main { // find(1); //} //} /* import java.util.*; public class Main { public Main() { Scanner t = new Scanner(System.in); String str = t.next(); char chr[] = new char[str.length()+1]; for(int i=0; i<str.length(); i++) { chr[i+1] = str.charAt(i); } int y = str.length(); find(1,y); } private void find(int i, int y) { // TODO Auto-generated method stub if(i<=y) { this.find(i*2, y); System.out.println(i); this.find(i*2+1, y); } } public static void main(String[] args) { new Main(); } } */ import java.util.*; class DbLinkedList<E>{ class Node<E>{ private E data; private Node<E> prev; private Node<E> next; public Node() { prev = next = this; } Node } } public class Main{ public Main() { } public static void main(String[] args) { new Main(); } }

/* //반 애들 이름 입력하기 import java.util.*; public class Main{ class LinkedList<E>{ class Node<E>{ private E data; private Node<E> next; Node(E data, Node<E> next){ this.data = data; this.next = next; } } private Node<E> head; private Node<E> crnt; //로 조지기 private Node<E> pre; private Node tail; public void add(String x) { Node v = new Node(x, null); v.next = head.next; head.next = v; crnt.next = v; } public LinkedList() { head.next = tail; crnt.next = tail; tail = null; } public void no() { if(head.next!=null) { pre = head.next; if(pre.next != null) { pre = pre.next; }else { crnt = pre; } } } } public Main() { Scanner s = new Scanner(System.in); int x = s.nextInt(); String[] arr = new String[x]; LinkedList li = new LinkedList(); for(int i=0; i<arr.length; i++) { System.out.print("이름을 입력하세요 :"); arr[i] = s.nextLine(); li.add(arr[i]); } } public static void main(String[] args) { new Main(); } } */ import java.util.*; class LinkedList<E>{ class Node{ private String data; private Node next; public Node(String data, Node Next) { this.data = data; this.next = Next; } } private Node head; private Node tail; private Node crnt; private Node pre; public void add(String x) { Node v = new Node(x, null); v.next = head.next; head.next = v; crnt.next = v; } public void pop() { if(head.next != null) { pre = head.next; if(pre.next != null) { pre = pre.next; }else { crnt = pre; pre = null; } } } public void see() { if(head.next != null) { pre=head.next; System.out.println(pre.data); if(pre.next != null) { pre = pre.next; System.out.println(pre.data); }else { crnt = pre; } } } public LinkedList(){ head.next= tail; crnt.next= tail; tail = null; } } public class Main{ public Main() { Scanner s = new Scanner(System.in); int x = s.nextInt(); LinkedList lis = new LinkedList(); String[] str = new String[x]; for(int i=0; i<str.length; i++) { System.out.println("이름을 입력하세요 : "); str[i]=s.nextLine(); lis.add(str[i]); } } public static void main(String[] args) { new Main(); } }

/* import java.util.*; public class Main{ public Main() { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int count =0; for(;;) { if(n>=500) { n=n-500; count ++; } else if(n<500 && n>=100) { n=n-100; count ++; } else if(n<100 && n>=50) { n=n-50; count ++; } if(n<50 && n>=10) { n=n-10; count ++; } if(n==0) { break; } } System.out.println(count); } public static void main(String[] args) { new Main(); } } */ /* import java.util.*; public class Main{ public Main() { Scanner s = new Scanner(System.in); int [] arr = new int [3]; for(int i=0; i<arr.length; i++) { arr[i]=s.nextInt(); //0 = 배열의 크기 , 1=숫자가 더해지는 횟수, 2= 큰 수의 법칙 k } int [] brr = new int [arr[0]]; for(int i=0; i<brr.length; i++) { brr[i]=s.nextInt(); } Arrays.sort(brr); int sum=0; while(arr[1]!=0) { for(int i=0; i<arr[2]; i++) { sum+=brr[0]; } sum += brr[1]; arr[1]-=arr[2]; } System.out.print(sum); } //max에 가장 큰 수 public static void main(String[] args) { new Main(); } } */ /* import java.util.*; public class Main{ public Main() { Scanner s = new Scanner(System.in); int [][] arr; int n = s.nextInt(); int m = s.nextInt(); int [] arr1 = new int [m]; int [] brr1 = new int [m]; arr = new int [n][m]; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { arr[i][j]=s.nextInt(); } } for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { arr1[j] = arr[i][j]; } Arrays.sort(arr1); brr1[i]=arr1[0]; } Arrays.sort(brr1); System.out.println(brr1[m-1]); } public static void main(String [] args) { new Main(); } } */ /* import java.util.*; public class Main{ public Main() { Scanner s = new Scanner(System.in); int n = s.nextInt(); int k = s.nextInt(); int count =0; while(n!=1) { if(n%k==0) { n=n/k; count ++; } else { n -= 1; count ++; } } System.out.print(count); } public static void main(String[] args) { new Main(); } } */ /* 질문 import java.util.*; public class Main{ public Main() { Scanner s = new Scanner(System.in); int n = s.nextInt(); int x=1; int y=1; String al= s.next() ; String[] sl = new String[al.length()]; sl=al.split(" "); for(int i=0; i<sl.length; i++) { if(sl[i].equals("R")&&x!=n) { x++; }else if(sl[i].equals("U")&&y!=1) { y--; }else if(sl[i].equals("D")&&y!=n) { y++; }else if(sl[i].equals("L")&&x!=1){ x--; } } System.out.print(x+" "+y); } public static void main(String [] args) { new Main(); } } */ /* 완전탐색함 다른 방법을 원함 import java.util.*; public class Main{ public Main() { Scanner s = new Scanner(System.in); int n = s.nextInt(); int count=0; int i=0; int [] arr = new int[6]; for(int j=0; j<6; j++) { if(j%2==0&&j<=4) { while(arr[j]!=10) { arr[j]+=1; if(arr[j]==3){ count ++; } } }else { while(arr[j]!=6) { arr[j]+=1; }if(arr[j]==3) { count++; } } } } public static void main(String[] args) { new Main(); } } */ import java.util.*; class LinkedList{ class Node{ private int data; private Node next; Node (int data, Node Next){ this.data = data; this.next = next; } } private Node head; private Node crnt; private Node tail; public void add(int x) { Node v = new Node(x, null); v.next = head.next; crnt.next = v; head.next = v; } public LinkedList() { head.next = tail; crnt.next = tail; tail=null; } } public class Main{ public static void main(String[] args) { LinkedList data = new LinkedList(); Scanner s = new Scanner(System.in); while(true) { int v = s.nextInt(); data.add(v); } } }

import java.util.*; class LinkedList { class Node{ private int data; //데이터 private Node next; // 뒤쪽 포인터 Node(int data, Node next){ this.data = data; this.next = next; } } private Node head; //머리노드 private Node crnt; //선택 노드 private Node tail; public void add(int x) { Node v = new Node(x, null); v.next = head.next; crnt.next = v; head.next = v; } public void delete() { } public LinkedList() { head.next = tail; crnt.next = tail; tail = null; } } public class Main { public static void main(String[] args){ LinkedList data = new LinkedList(); Scanner s = new Scanner(System.in); while(true) { int v = s.nextInt(); data.add(v); } } }

/* import java.util.*; class circle{ int front=0; int rear=0; int max=0; int q[]; public circle(int capacity) { try { max = capacity; q=new int[max]; }catch(OutOfMemoryError e) { max = 0; } } public void enqueue(int x) { q[front]=x; front ++; front = front % max; if(rear==front) { System.out.println("full"); } } public void dequeue() { rear++; rear = rear%max; if(rear==front) { System.out.println("empty"); } } public void view() { for(int i=0; i<max; i++) { System.out.print(q[i]); if(i==max-1)System.out.print("\n"); } } } class queue{ int front=0; int rear=0; int max=0; int q[]; public queue(int capacity){ try { max = capacity; q = new int[max]; }catch(OutOfMemoryError e) { max=0; } } public int enqueue(int x){ return q[front++]=x; } public void dequeue() { q[rear++]=0; if(rear==front) { System.out.print("비어있습니다"); rear=0; front=0; } } public void view() { for(int i=0; i<max; i++) { System.out.print(q[i]); if(i==max-1)System.out.print("\n"); } } public void clean() { for(int i=rear; i<front; i++) { for(int j=0; j<front-rear; j++) { q[j]=q[i]; } } front = front-rear; rear=0; } } public class Main{ public Main() { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); circle c = new circle(n); for(int i=0 ; i<n; i++) { int x = scan.nextInt(); c.enqueue(x); c.view(); } for(int i=0; i<5; i++) { c.dequeue(); } c.view(); } public static void main(String[] args) { new Main(); } } */ import java.util.*; class LinkedList<E>{ class Node<E>{ private E data;//데이터 private Node<E> next; Node(E data, Node<E> next){ this.data= data; this.next= next; } } private Node<E> head; private Node<E> crnt; } public class Main{ public Main() { } public static void main(String[] args) { new Main(); } }

/* import java.util.*; class IntStack extends Stack{ int ptr=0; int max; int[] stk; public IntStack(int capacity) { max = capacity; try { stk = new int [max]; }catch(OutOfMemoryError e) { max=0; } } public class EmptyIntStackException extends RuntimeException{ public EmptyIntStackException() { } } public class OverflowIntStackException extends RuntimeException{ public OverflowIntStackException() { } } public int push(int x) throws OverflowIntStackException{ if(ptr>=max) throw new OverflowIntStackException(); return stk[ptr++]=x; } public int po() throws EmptyIntStackException{ if (ptr <= 0) throw new EmptyIntStackException(); return stk[--ptr]; } public int top() { if(ptr==0) { return -1; } return stk[ptr-1]; } public int size() { return ptr; } public int empt() { if(ptr==0) { return 1; } else { return 0; } } } public class Main{ public Main() { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); IntStack s = new IntStack(n); for(int i=0; i<n; i++) { String str= scan.nextLine(); String[] arr = new String[2]; arr = str.split(" "); if(arr[0].equals("push")) { s.push(Integer.valueOf(arr[1])); }else if(str.equals("pop")) { s.po(); }else if(str.equals("empty")) { s.empt(); }else if(str.equals("size")) { s.size(); }else if(str.equals("top")) { s.top(); } } } public static void main(String[] args) { new Main(); } } */ /* import java.util.*; public class Main{ Random rd = new Random(); Scanner scan = new Scanner(System.in); public Main() { int n = (rd.nextInt(5)-1)%5; int n1 =rd.nextInt(5)-1; int n2 =(rd.nextInt(5)-1)%5; String[] str = new String[6]; for(int i=0; i<5; i++) { str[i] = scan.nextLine(); } System.out.print(str[n]); System.out.print(str[n1]); System.out.print(str[n2]); } public static void main(String[] args) { new Main(); } } */ /* interface ma{ void ma1(); } class ma1 implements ma{ @Override public void ma1() { // TODO Auto-generated method stub } } public class Main{ public Main() { } public static void main(String[] args) { new Main(); } } */ /* import java.util.*; interface management{ int push(int capacity); int pop(); class OverflowIntStackException extends RuntimeException{}; class EmptyIntStackException{}; } class choi implements management{ @Override public int push(int capacity) { // TODO Auto-generated method stub return 0; } @Override public int pop() { // TODO Auto-generated method stub return 0; } class OverflowIntStackException extends Runtime{ public OverflowIntStackException() { } } } public class Main{ public Main() { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); // 학생수 } public static void main(String[] args) { new Main(); } } */ /* import java.util.*; public class Main{ public Main() { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[] arr = new int [n]; String[] str= new String[n]; for(int i=0; i<n; i++) { str[i] = scan.nextLine(); arr[i] = scan.nextInt(); } for(int j=0; j<n; j++) { for(int i=0; i<arr[j]; i++) { } } } public static void main(String[] args) { new Main(); } } */

/* import java.util.*; public class Main{ public Main() { Scanner scan = new Scanner(System.in); String input = scan.nextLine(); String [] sp1 = input.split(" "); int[] st = new int[200]; int top=0; char[] op = new char[2000]; int opTop=0; for(int i=0; i<sp1.length; i++) { if(sp1[i].equals("+") ||sp1[i].equals("-") || sp1[i].equals("*")) { if(opTop==0) { //연산자가 처음으로 들어올때 op[opTop++] = sp1[i].charAt(0); } else if(op[opTop-1]=='*'){ // 그 전에 들어가 있는 것이 *일때 if(sp1[i].charAt(0)=='+'||sp1[i].charAt(0)=='-') { //그 후에 들어올 것이 +-일때 op[opTop-1] = sp1[i].charAt(0); top--; int b = st[top]; st[top] = 0; top--; int a = st[top]; st[top] = 0; int c = a*b; st[top] = c; top++; }else if(sp1[i].charAt(0)=='*') { //그 후에 들어올 것이 *일때 op[opTop-1]=sp1[i].charAt(0); opTop++; } } else{ op[opTop-1]=sp1[i].charAt(0); } }else { st[top]=Integer.valueOf(sp1[i]); top++; } } for(int i=opTop-1; i>=0; i--) { if(op[i]=='*') { top--; int b = st[top]; top--; int a = st[top]; int c =a*b; st[top]=c; top++; } else if(op[i]=='+') { top--; int b = st[top]; top--; int a= st[top]; int c= b+a; st[top]=c; top++; }else { top--; int b = st[top]; top--; int a= st[top]; int c= b-a; st[top]=c; top++; } } System.out.println(st[0]); } public static void main(String[] args) { new Main(); } } */ /* import java.util.*; public class Main{ public Main() { Scanner scan = new Scanner(System.in); String input = scan.nextLine(); String [] sp1 = input.split(" "); int[] st = new int[200]; int top=0; //data가 들어갈 위치 for(int i=0; i<sp1.length; i++) { if(sp1[i].equals("+") ||sp1[i].equals("-") || sp1[i].equals("*")) { if(sp1[i].equals("+")) { int b= st[--top]; int a = st[--top]; st[top++]=b+a; }else if(sp1[i].equals("-")) { int b= st[--top]; int a = st[--top]; st[top++] = a-b; }else{ int b= st[--top]; int a = st[--top]; st[top++]=b*a; } } else { st[top++]=Integer.valueOf(sp1[i]); } } System.out.println(st[top-1]); } public static void main(String[] args) { new Main(); } } */ /* import java.util.*; class intStack{ int max; int ptr; int[] stk; public intStack(int capacity) { ptr = 0; max = capacity; try { stk= new int[max]; } catch(OutOfMemoryError e) { max =0; } } public void push(int x) { if(ptr>=max) { throw new OverflowIntStackException(); } stk[ptr++] = x; } public class OverflowIntStackException extends RuntimeException{ public OverflowIntStackException() { } } public void finish() { for(int i=ptr-1; i>=0; i--) { if(i%3==2) System.out.print(','); System.out.print(stk[i]); } } } public class Main{ Scanner scan = new Scanner(System.in); public Main() { int n= 8; //int n = scan.nextInt(); intStack s = new intStack(n); String arr = scan.nextLine(); char[] arr1 = new char[n]; arr1 = arr.toCharArray(); for(int i=0; i<n; i++) { //System.out.println(arr1[i]); s.push(Character.getNumericValue(arr1[i])); } s.finish(); } public static void main(String[] args) { new Main(); } } */ import java.util.*; class IntStack{ int ptr; int max; int[] stk; public IntStack(int capacity) { ptr=0; max=capacity; try { stk = new int [max]; }catch(OutOfMemoryError e) { max=0; } } public class OverflowIntStackException extends RuntimeException{ public OverflowIntStackException() { } } public class EmptyIntStackException extends RuntimeException{ public EmptyIntStackException() { } } public int push(int x) throws OverflowIntStackException { if(ptr>=max) { throw new OverflowIntStackException(); } return stk[ptr++]=x; } public int pop() throws EmptyIntStackException{ if(ptr<=0) { throw new EmptyIntStackException(); } return stk[--ptr]; } public int top() { if(ptr==0) return -1; return stk[ptr-1]; } public boolean empty() { if(ptr==0) return true; return false; } public int size() { return max; } } public class Main{ public Main() { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); IntStack s = new IntStack(n); for(int i=0; i<n; i++) { String input = scan.nextLine(); String [] sp1 = input.split(" "); if(sp1[0].equals("push(")) { s.push(Integer.valueOf(sp1[1])); } else if(sp1[0].equals("pop()")) { s.pop(); } else if(sp1[0].equals("top()")) { s.top(); } else if(sp1[0].equals("size()")) { s.size(); } else { s.empty(); } } } public static void main(String[] args) { new Main(); } }

/* import java.util.*; class IntStack{ int ptr; int[] stk; int max; public IntStack(int capacity) { ptr=0; max = capacity; try { stk = new int [max]; }catch(OutOfMemoryError e) { max=0; } } public class EmptyIntStackException extends RuntimeException{ public EmptyIntStackException(){ } } public class OverflowIntStackException extends RuntimeException{ public OverflowIntStackException() { } } public int push(int x)throws OverflowIntStackException{ if(ptr>=max) { throw new OverflowIntStackException(); } return stk[ptr++]=x; } public int pop() { if(ptr<=0) { throw new EmptyIntStackException(); } return stk[--ptr]; } public int top() { return ptr; } public int size() { return max; } public boolean empty() { if(ptr==0) { return true; } return false; } } public class Main { public Main(){ Scanner scan = new Scanner(System.in); int n = scan.nextInt(); IntStack stack = new IntStack(n); for(int i=0; i<n; i++) { String s = scan.nextLine(); if(s.equals("top()")) { stack.top(); }else if(s.equals("pop()")) { stack.pop(); }else if(s.equals("size()")) { stack.size(); }else if(s.equals("empty()")){ stack.empty(); }else{ int k = scan.nextInt(); stack.push(k); } } } public static void main(String[] args) { new Main(); } } */ /* import java.util.*; class IntStack{ int ptr; int[] stk; int max; public IntStack(int capacity) { ptr=0; max = capacity; try { stk = new int [max]; }catch(OutOfMemoryError e) { max=0; } } public class EmptyIntStackException extends RuntimeException{ public EmptyIntStackException(){ } } public class OverflowIntStackException extends RuntimeException{ public OverflowIntStackException() { } } public int push(int x)throws OverflowIntStackException{ if(ptr>=max) { throw new OverflowIntStackException(); } return stk[ptr++]=x; } public int pop() { if(ptr<=0) { throw new EmptyIntStackException(); } return stk[--ptr]; } public int top() { return ptr; } public int size() { return max; } public boolean empty() { if(ptr==0) { return true; } return false; } public void sum() { int sum =0; for(int i=0; i<ptr; i++) { sum += stk[i]; } System.out.println(sum); } } public class Main { public Main() { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); IntStack stk = new IntStack(n); int[] arr = new int[n]; for(int i=0; i<n; i++) { arr[i] = scan.nextInt(); if(arr[i]!=0) { stk.push(arr[i]); }else { stk.pop(); } } stk.sum(); } public static void main(String[] args) { new Main(); } } */ //import java.util.*; // //class IntStack{ // int ptr; // int max; // int[] stk; // public IntStack(int capacity) { // ptr = 0; // max = capacity; // try { // stk = new int[max]; // }catch(OutOfMemoryError e) { // max =0; // } // } // public class EmptyIntStackException extends RuntimeException{ // public EmptyIntStackException(){ // // } // } // public class OverflowIntStackException extends RuntimeException{ // public OverflowIntStackException() { // // } // } // // public int push(int x)throws OverflowIntStackException{ // if(ptr>=max) { // throw new OverflowIntStackException(); // } // return stk[ptr++] =x; // } // public int pop() throws EmptyIntStackException{ // if(ptr<=0) { // throw new EmptyIntStackException(); // } // return stk[--ptr]; // } //} // //public class Main{ // public Main() { // Scanner scan = new Scanner(System.in); // int n = scan.nextInt(); // // // } // public static void main(String[] args) { // new Main(); // } //} import java.util.*; public class Main { public static void main(String[] args) { Scanner t = new Scanner(System.in); String input = t.nextLine(); String []sp1 = input.split(" "); int[] temp = new int[200]; int numTop=0; char[] op = new char[2000]; int opTop=0; for(int i=0; i<sp1.length; i++) { if(sp1[i].equals("+") || sp1[i].equals("-") || sp1[i].equals("*")) { if(opTop==0) { op[opTop++] = sp1[i].charAt(0); } else if(op[opTop-1]=='*'){ if(sp1[i].charAt(0)=='+'||sp1[i].charAt(0)=='-') { op[opTop-1] = sp1[i].charAt(0); numTop--; int b = temp[numTop]; temp[numTop] = 0; numTop--; int a = temp[numTop]; temp[numTop] = 0; int c = a*b; temp[numTop] = c; numTop++; } } else { } }else { temp[numTop]=Integer.valueOf(sp1[i]); numTop++; } } if(op[opTop]=='+') { temp[numTop-1]=temp[numTop-1]+temp[numTop-2]; numTop--; }else { temp[numTop-1]=temp[numTop-2]-temp[numTop-1]; numTop--; } for(int i=0; i<numTop; i++) { System.out.println(temp[i]); } System.out.println(temp[numTop]); } }

/* class IntStack{ int max; // 스택 용량 int ptr; // 스택 포인터 int[] stk; // 스택의 본체 public IntStack(int capacity) { int ptr =0; int max = capacity; try { stk = new int[max]; }catch(OutOfMemoryError e) { max = 0; } } public class EmptyIntStackException extends RuntimeException{ public EmptyIntStackException() { } } public class OverflowIntStackException extends RuntimeException{ public OverflowIntStackException() { } } public int push(int x) throws OverflowIntStackException{ if(ptr>=max) throw new OverflowIntStackException(); return stk[ptr++] = x; } public int pop() throws EmptyIntStackException{ if(ptr<=0) throw new EmptyIntStackException(); return stk[--ptr]; } public int peek() throws EmptyIntStackException{ if(stk[ptr]<=0) throw new EmptyIntStackException(); return stk[ptr-1]; } public int indexOf(int i) { for(int j=ptr-1 ; j>=0; j --) { if(stk[j]==i) { return j; } } return -1; } public void clear() { ptr = 0; } public int capacity() { return max; } public int size() { return ptr; } public boolean IsEmpty() { if(ptr==0) { return true; } return false; } public boolean IsFull() { if(ptr==max) { return true; } return false; } public void dump() { if(ptr!=0) { for(int j = ptr-1 ; j >=0; j--) { System.out.println(stk[j]); } }else { System.out.println("스택이 비어있습니다."); } } } */ // 2016 : 천단위 구분 기호 문제 import java.util.*; class intStack{ int max; int ptr; int[] stk; public intStack(int capacity) { ptr = 0; max = capacity; try { stk= new int[max]; } catch(OutOfMemoryError e) { max =0; } } public void push(int x) { if(ptr>=max) { throw new OverflowIntStackException(); } stk[ptr++] = x; } public class OverflowIntStackException extends RuntimeException{ public OverflowIntStackException() { } } public void finish() { for(int i=ptr-1; i>=0; i--) { if(i%3==2) System.out.print(','); System.out.print(stk[i]); } } } public class Main{ Scanner scan = new Scanner(System.in); public Main() { int n= 8; //int n = scan.nextInt(); intStack s = new intStack(n); String arr = scan.nextLine(); char[] arr1 = new char[n]; arr1 = arr.toCharArray(); for(int i=0; i<n; i++) { //System.out.println(arr1[i]); s.push(Character.getNumericValue(arr1[i])); } s.finish(); } public static void main(String[] args) { new Main(); } } /* import java.util.*; class IntStack{ int max; int ptr; int[] stk; public IntStack(int capacity) { int ptr = 0; int max = capacity; try { stk = new int[max]; }catch(OutOfMemoryError e) { max = 0; } } public class EmptyIntStackException extends RuntimeException{ public EmptyIntStackException() { } } public class OverflowIntStackException extends RuntimeException{ public OverflowIntStackException() { } } public int push(int x) throws OverflowIntStackException { if(ptr>=max) { throw new OverflowIntStackException(); } return stk[ptr++] = x; } public int top() { if(ptr<=0) return -1; return ptr; } public int pop() throws EmptyIntStackException{ if(ptr<=0) throw new EmptyIntStackException(); return stk[ptr--]; } public int size() { return ptr; } public boolean empty() { if(ptr==0) return true; return false; } } public class Main{ public Main() { Scanner scan = new Scanner(System.in); int x = scan.nextInt(); int i=0; IntStack s = new IntStack(x); } public static void main(String[] args) { new Main(); } } */