## CF Solutions 21-40 ∞

release

```
选择题目的顺序是按照CodeForces上面Sovled排序而得到的。
该文档中包含前21-40道题目的解题方法和相应Python代码，他们分别是：
110A 236A 281A 339A 144A 266B 271A 136A 268A 263A
122A 61A 237A 69A 141A 268B 58A 155A 118B 208A
```

##### 关于Sample Test样式的问题

目前我是直接用的pygments bash类型来对test进行处理，实际上我觉得input和output如果能带上颜色，那么会更直观一些。

如果有人对Hacking For Pygments感兴趣，可以试着增加对input和output的过滤识别并上色，或者也可以试着尝试一下pygments支持的哪种语言可以对其上色。

# 110A Nearly Lucky Number

Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Unfortunately, not all numbers are lucky. Petya calls a number nearly lucky if the number of lucky digits in it is a lucky number. He wonders whether number n is a nearly lucky number.

Input

The only line contains an integer n (1 ≤ n ≤ 10**18). Please do not use the %lld specificator to read or write 64-bit numbers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

Output

Print on the single line "YES" if n is a nearly lucky number. Otherwise, print "NO" (without the quotes).

Note

In the first sample there are 3 lucky digits (first one and last two), so the answer is "NO".

In the second sample there are 7 lucky digits, 7 is lucky number, so the answer is "YES".

In the third sample there are no lucky digits, so the answer is "NO".

#### Sample test(s):

```
input
40047
output
NO
input
7747774
output
YES
input
1000000000000000000
output
NO
```

#### Code:

```
#实际上就是统计出现4或者7的位数的个数是否为4或7
import sys
number = sys.stdin.readline().strip()
flag = True
#用n来记录出现4或者7的个数
n = 0
for i in range(len(number)):
digit = number[i]
if digit in "47":
n += 1
if str(n) in "47":
print "YES"
else:
print "NO"
```

# 236A Boy or Girl

Those days, many boys use beautiful girls' photos as avatars in forums. So it is pretty hard to tell the gender of a user at the first glance. Last year, our hero went to a forum and had a nice chat with a beauty (he thought so). After that they talked very often and eventually they became a couple in the network.

But yesterday, he came to see "her" in the real world and found out "she" is actually a very strong man! Our hero is very sad and he is too tired to love again now. So he came up with a way to recognize users' genders by their user names.

This is his method: if the number of distinct characters in one's user name is odd, then he is a male, otherwise she is a female. You are given the string that denotes the user name, please help our hero to determine the gender of this user by his method.

Input

The first line contains a non-empty string, that contains only lowercase English letters — the user name. This string contains at most 100 letters.

Output

If it is a female by our hero's method, print "CHAT WITH HER!" (without the quotes), otherwise, print "IGNORE HIM!" (without the quotes).

Note

For the first example. There are 6 distinct characters in "wjmzbmr". These characters are: "w", "j", "m", "z", "b", "r". So wjmzbmr is a female and you should print "CHAT WITH HER!".

#### Sample test(s):

```
input
wjmzbmr
output
CHAT WITH HER!
input
xiaodao
output
IGNORE HIM!
input
sevenkplus
output
CHAT WITH HER!
```

#### Code:

```
#统计输入的名字不重复的字母有多少个
#如果是偶数个，则输出"CHAT WITH HER!"
#如果是基数个，则输出"IGNORE HIM!"
import sys
inputs = sys.stdin.readline().strip()
distinctN = ""
for i in range(len(inputs)):
char = inputs[i]
if char not in distinctN:
distinctN = distinctN + char
if len(distinctN) % 2 == 0:
print "CHAT WITH HER!"
else:
print "IGNORE HIM!"
```

# 281A Word Capitalization

Capitalization is writing a word with its first letter as a capital letter. Your task is to capitalize the given word.

Note, that during capitalization all the letters except the first one remains unchanged.

Input

A single line contains a non-empty word. This word consists of lowercase and uppercase English letters. The length of the word will not exceed 103.

Output

Output the given word after capitalization.

#### Sample test(s):

```
input
ApPLe
output
ApPLe
input
konjac
output
Konjac
```

#### Code:

```
#直接将输入的字符串第一个字母大写再输出出去
#史上最简单题目，没有之一，不用解释==！
import sys
inputs = sys.stdin.readline().strip()
print inputs[0].upper() + inputs[1:]
```

# 339A Helpful Maths

Xenia the beginner mathematician is a third year student at elementary school. She is now learning the addition operation.

The teacher has written down the sum of multiple numbers. Pupils should calculate the sum. To make the calculation easier, the sum only contains numbers 1, 2 and 3. Still, that isn't enough for Xenia. She is only beginning to count, so she can calculate a sum only if the summands follow in non-decreasing order. For example, she can't calculate sum 1+3+2+1 but she can calculate sums 1+1+2 and 3+3.

You've got the sum that was written on the board. Rearrange the summans and print the sum in such a way that Xenia can calculate the sum.

Input

The first line contains a non-empty string s — the sum Xenia needs to count. String s contains no spaces. It only contains digits and characters "+". Besides, string s is a correct sum of numbers 1, 2 and 3. String s is at most 100 characters long.

Output

Print the new sum that Xenia can count.

#### Sample test(s):

```
input
3+2+1
output
1+2+3
input
1+1+3+1+3
output
1+1+1+3+3
input
2
output
2
```

#### Code:

```
#该题目要求将加法多项式转换成按被加数有序递增的加法多项式
import sys
#将输入按照"+"切割成数组
inputs = sys.stdin.readline().strip().split("+")
#数组排序
inputs.sort()
#重新拼接成字符串并输出
print "+".join(inputs)
```

# 144A Arrival of the General

A Ministry for Defense sent a general to inspect the Super Secret Military Squad under the command of the Colonel SuperDuper. Having learned the news, the colonel ordered to all n squad soldiers to line up on the parade ground.

By the military charter the soldiers should stand in the order of non-increasing of their height. But as there's virtually no time to do that, the soldiers lined up in the arbitrary order. However, the general is rather short-sighted and he thinks that the soldiers lined up correctly if the first soldier in the line has the maximum height and the last soldier has the minimum height. Please note that the way other solders are positioned does not matter, including the case when there are several soldiers whose height is maximum or minimum. Only the heights of the first and the last soldier are important.

For example, the general considers the sequence of heights (4, 3, 4, 2, 1, 1) correct and the sequence (4, 3, 1, 2, 2) wrong.

Within one second the colonel can swap any two neighboring soldiers. Help him count the minimum time needed to form a line-up which the general will consider correct.

Input

The first input line contains the only integer n (2 ≤ n ≤ 100) which represents the number of soldiers in the line. The second line contains integers a1, a2, ..., an (1 ≤ ai ≤ 100) the values of the soldiers' heights in the order of soldiers' heights' increasing in the order from the beginning of the line to its end. The numbers are space-separated. Numbers a1, a2, ..., an are not necessarily different.

Output

Print the only integer — the minimum number of seconds the colonel will need to form a line-up the general will like.

Note

In the first sample the colonel will need to swap the first and second soldier and then the third and fourth soldier. That will take 2 seconds. The resulting position of the soldiers is (44, 33, 22, 11).

In the second sample the colonel may swap the soldiers in the following sequence:

(10, 10, 58, 31, 63, 40, 76)

(10, 58, 10, 31, 63, 40, 76)

(10, 58, 10, 31, 63, 76, 40)

(10, 58, 10, 31, 76, 63, 40)

(10, 58, 31, 10, 76, 63, 40)

(10, 58, 31, 76, 10, 63, 40)

(10, 58, 31, 76, 63, 10, 40)

(10, 58, 76, 31, 63, 10, 40)

(10, 76, 58, 31, 63, 10, 40)

(76, 10, 58, 31, 63, 10, 40)

(76, 10, 58, 31, 63, 40, 10)

#### Sample test(s):

```
input
4
33 44 11 22
output
2
input
7
10 10 58 31 63 40 76
output
10
```

#### Code:

```
#给定一个包含n个士兵身高的队列
#身高最高的在最左边，身高最矮的在最右边
#输出最少的调整位置的次数，每次只能临着的两个互换
#
#其实就在从左到由，记录第一次出现的最高身高位置和最后一次出现得到最矮身高位置
#如果最高身高位置大于最矮身高位置，则少一次互换过程(因为他俩互换多算了一次)
import sys
soilderCount = int(sys.stdin.readline())
inputs = sys.stdin.readline().split()
sHeights = []
for i in range(soilderCount):
sHeights.append(int(inputs[i]))
maxIndex = sHeights.index(max(sHeights))
minHeight = min(sHeights)
minIndex = 0
for i in range(soilderCount):
if sHeights[i] == minHeight:
minIndex = i
if(maxIndex > minIndex):
print maxIndex + soilderCount - minIndex - 2
else:
print maxIndex + soilderCount - minIndex -1
```

# 266B Queue at the School

During the break the schoolchildren, boys and girls, formed a queue of n people in the canteen. Initially the children stood in the order they entered the canteen. However, after a while the boys started feeling awkward for standing in front of the girls in the queue and they started letting the girls move forward each second.

Let's describe the process more precisely. Let's say that the positions in the queue are sequentially numbered by integers from 1 to n, at that the person in the position number 1 is served first. Then, if at time x a boy stands on the i-th position and a girl stands on the (i + 1)-th position, then at time x + 1 the i-th position will have a girl and the (i + 1)-th position will have a boy. The time is given in seconds.

You've got the initial position of the children, at the initial moment of time. Determine the way the queue is going to look after t seconds.

Input

The first line contains two integers n and t (1 ≤ n, t ≤ 50), which represent the number of children in the queue and the time after which the queue will transform into the arrangement you need to find.

The next line contains string s, which represents the schoolchildren's initial arrangement. If the i-th position in the queue contains a boy, then the i-th character of string s equals "B", otherwise the i-th character equals "G".

Output

Print string a, which describes the arrangement after t seconds. If the i-th position has a boy after the needed time, then the i-th character a must equal "B", otherwise it must equal "G".

#### Sample test(s):

```
input
5 1
BGGBG
output
GBGGB
input
5 2
BGGBG
output
GGBGB
input
4 1
GGGB
output
GGGB
```

#### Code:

```
#输入为一个队列，站着男孩和女孩，B for Boy, G for Girl
#男孩觉得不好意思，每隔一个时间段，男孩会让后面的女孩站到自己的前面去
#第一行输入为总人数n和经过了t个时间段
#第二行输入为初始男孩女孩所战队列的样子
#输出经过t个时间段以后，队列的样子
import sys
inputs = sys.stdin.readline().split()
n = int(inputs[0])
t = int(inputs[1])
sQueue = sys.stdin.readline().strip()
for sec in range(t):
flag = False
for i in range(n):
if flag:
flag = False
continue
#如果当前是男孩，并且他不是最后一个人，并且他后面是女孩的话
#他和女孩互换位置
if sQueue[i] == "B" and i != n -1 and sQueue[i+1] == "G":
sQueue = sQueue[:i] + sQueue[i+1] + sQueue[i] + sQueue[i+2:]
flag = True
print sQueue
```

# 271A Beautiful Year

It seems like the year of 2013 came only yesterday. Do you know a curious fact? The year of 2013 is the first year after the old 1987 with only distinct digits.

Now you are suggested to solve the following problem: given a year number, find the minimum year number which is strictly larger than the given one and has only distinct digits.

Input

The single line contains integer y (1000 ≤ y ≤ 9000) — the year number.

Output

Print a single integer — the minimum year number that is strictly larger than y and all it's digits are distinct. It is guaranteed that the answer exists.

#### Sample test(s):

```
input
1987
output
2013
input
2013
output
2014
```

#### Code:

```
#给定输入年份计算下一个拥有不同数字的年份是多少
import sys
#定义检测当前年份是否由不同数字组成的函数
#如果数字均不相同则返回True，比如1987包含1,9,8,7四个不同数字
#如果数字有相同则返回False，比如1988包含1，9和2个8
def checkBeautifulYear(yearN):
yearN = str(yearN)
if(yearN[0] in yearN[1:]): return False
if(yearN[1] in yearN[0] + yearN[2:]): return False
if(yearN[2] in yearN[:2] + yearN[3]): return False
if(yearN[3] in yearN[:3]): return False
return True
yearN = int(sys.stdin.readline())
#循环判断，根据当前输入年份找到下一个包含不同数字的年份
while True:
yearN = yearN + 1
if checkBeautifulYear(yearN):
print yearN
break
```

# 136A Presents

Little Petya very much likes gifts. Recently he has received a new laptop as a New Year gift from his mother. He immediately decided to give it to somebody else as what can be more pleasant than giving somebody gifts. And on this occasion he organized a New Year party at his place and invited n his friends there.

If there's one thing Petya likes more that receiving gifts, that's watching others giving gifts to somebody else. Thus, he safely hid the laptop until the next New Year and made up his mind to watch his friends exchanging gifts while he does not participate in the process. He numbered all his friends with integers from 1 to n. Petya remembered that a friend number i gave a gift to a friend number pi. He also remembered that each of his friends received exactly one gift.

Now Petya wants to know for each friend i the number of a friend who has given him a gift.

Input

The first line contains one integer n (1 ≤ n ≤ 100) — the quantity of friends Petya invited to the party. The second line contains n space-separated integers: the i-th number is pi — the number of a friend who gave a gift to friend number i. It is guaranteed that each friend received exactly one gift. It is possible that some friends do not share Petya's ideas of giving gifts to somebody else. Those friends gave the gifts to themselves.

Output

Print n space-separated integers: the i-th number should equal the number of the friend who gave a gift to friend number i.

#### Sample test(s):

```
input
4
2 3 4 1
output
4 1 2 3
input
3
1 3 2
output
1 3 2
input
2
1 2
output
1 2
```

#### Code:

```
#这道题第一行输入表示有多少个人参加互送礼品的聚会
#第二行表示每个人分别把礼物送给了谁
#要求输出的是每个人的礼物都是谁送的==！
'''
4
2 3 4 1
4表示总共有4个人
·2·表示1号送给了2号礼物
·3·表示2号送给了3号礼物
·4·表示3号送给了4号礼物
·1·表示4号送给了1号礼物
输出的是谁分别收到了谁的礼物，即
4 1 2 3
·4·表示1号收到了4号送的礼物
·1·表示2号收到了1号送的礼物
·2·表示3号收到了2号送的礼物
·3·表示4号收到了3号送的礼物
'''
import sys
peopleAmount = int(sys.stdin.readline())
gifts = sys.stdin.readline().split()
getGifts = ['0']*peopleAmount
#循环将读入的送礼物的人对应到getGifts数组中
#比如1号送给了4号礼物，那么是就上就是getGifts[4] = '1'
for i in range(peopleAmount):
getGifts[int(gifts[i])-1] = str(i+1)
print " ".join(getGifts)
```

# 268A Games

Manao works on a sports TV. He's spent much time watching the football games of some country. After a while he began to notice different patterns. For example, each team has two sets of uniforms: home uniform and guest uniform. When a team plays a game at home, the players put on the home uniform. When a team plays as a guest on somebody else's stadium, the players put on the guest uniform. The only exception to that rule is: when the home uniform color of the host team matches the guests' uniform, the host team puts on its guest uniform as well. For each team the color of the home and guest uniform is different.

There are n teams taking part in the national championship. The championship consists of n·(n - 1) games: each team invites each other team to its stadium. At this point Manao wondered: how many times during the championship is a host team going to put on the guest uniform? Note that the order of the games does not affect this number.

You know the colors of the home and guest uniform for each team. For simplicity, the colors are numbered by integers in such a way that no two distinct colors have the same number. Help Manao find the answer to his question.

Input

The first line contains an integer n (2 ≤ n ≤ 30). Each of the following n lines contains a pair of distinct space-separated integers hi, ai (1 ≤ hi, ai ≤ 100) — the colors of the i-th team's home and guest uniforms, respectively.

Output

In a single line print the number of games where the host team is going to play in the guest uniform.

Note

In the first test case the championship consists of 6 games. The only game with the event in question is the game between teams 2 and 1 on the stadium of team 2.

In the second test sample the host team will have to wear guest uniform in the games between teams: 1 and 2, 2 and 1, 2 and 3, 3 and 4, 4 and 2 (the host team is written first).

#### Sample test(s):

```
input
3
1 2
2 4
3 4
output
1
input
4
100 42
42 100
5 42
100 5
output
5
input
2
1 2
1 2
output
0
```

#### Code:

```
#当主场球队遇到客场球队球服颜色相同时，主场球队更换成客场球服
#统计有多少场比赛主场需要更换客场球服
#两层循环判断每个球队的主场球服和别的球队的客场球服相同的数量
#该数量就是主场球队需要更换球服的场次数，即最终结果
import sys
teamAmount = int(sys.stdin.readline())
team = [0]*teamAmount
for i in range(teamAmount):
inputs = sys.stdin.readline().split()
team[i] = inputs
result = 0
for i in range(teamAmount):
hostC = team[i][0]
for j in range(teamAmount):
if(i == j): continue
guestC = team[j][1]
if hostC == guestC: result += 1
print result
```

# 263A Beautiful Matrix

You've got a 5 × 5 matrix, consisting of 24 zeroes and a single number one. Let's index the matrix rows by numbers from 1 to 5 from top to bottom, let's index the matrix columns by numbers from 1 to 5 from left to right. In one move, you are allowed to apply one of the two following transformations to the matrix:

1. Swap two neighboring matrix rows, that is, rows with indexes i and i + 1 for some integer i (1 ≤ i < 5).

2. Swap two neighboring matrix columns, that is, columns with indexes j and j + 1 for some integer j (1 ≤ j < 5).You think that a matrix looks beautiful, if the single number one of the matrix is located in its middle (in the cell that is on the intersection of the third row and the third column). Count the minimum number of moves needed to make the matrix beautiful.

Input

The input consists of five lines, each line contains five integers: the j-th integer in the i-th line of the input represents the element of the matrix that is located on the intersection of the i-th row and the j-th column. It is guaranteed that the matrix consists of 24 zeroes and a single number one.

Output

Print a single integer — the minimum number of moves needed to make the matrix beautiful.

#### Sample test(s):

```
input
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
output
3
input
0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
output
1
```

#### Code:

```
#有一个5X5的矩阵，只有一个数字为1，其它数字都为0
#题目要求输入把1移动到矩阵中心最少要多少步
import sys
#首先获得1在矩阵中的位置
for i in range(5):
inputs = sys.stdin.readline()
if '1' in inputs:
inputs = inputs.split()
for j in range(5):
if inputs[j] == '1':
(x,y) = (i,j)
break
#直接输出该位置距离中心的距离就好了
#中心坐标为(2,2)(以0,0为起点)
#那么距离就是abs(x-2) + abs(y-2)
#abs()是python求绝对值的内置函数
print abs(x-2) + abs(y-2)
```

# 122A Lucky Division

Petya loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya calls a number almost lucky if it could be evenly divided by some lucky number. Help him find out if the given number n is almost lucky.

Input

The single line contains an integer n (1 ≤ n ≤ 1000) — the number that needs to be checked.

Output

In the only line print "YES" (without the quotes), if number n is almost lucky. Otherwise, print "NO" (without the quotes).

Note

Note that all lucky numbers are almost lucky as any number is evenly divisible by itself.In the first sample 47 is a lucky number. In the second sample 16 is divisible by 4.

#### Sample test(s):

```
input
47
output
YES
input
16
output
YES
input
78
output
NO
```

#### Code:

```
#本题要去判断输入的数字能否被Lucky Number整除
#因为输入范围为1~1000，所以直接先列出来这个范围内的luckyNumber再相除就好了
import sys
luckyN = [4,7,44,47,77,444,447,474,477,744,747,774,777]
inputN = int(sys.stdin.readline())
flag = True
for i in range(13):
if inputN % luckyN[i] == 0:
print "YES"
flag = False
break
if flag:
print "NO"
```

# 61A Ultra-Fast Mathematician

Shapur was an extremely gifted student. He was great at everything including Combinatorics, Algebra, Number Theory, Geometry, Calculus, etc. He was not only smart but extraordinarily fast! He could manage to sum 10**18 numbers in a single second.

One day in 230 AD Shapur was trying to find out if any one can possibly do calculations faster than him. As a result he made a very great contest and asked every one to come and take part.

In his contest he gave the contestants many different pairs of numbers. Each number is made from digits 0 or 1. The contestants should write a new number corresponding to the given pair of numbers. The rule is simple: The i-th digit of the answer is 1 if and only if the i-th digit of the two given numbers differ. In the other case the i-th digit of the answer is 0.

Shapur made many numbers and first tried his own speed. He saw that he can perform these operations on numbers of length ∞ (length of a number is number of digits in it) in a glance! He always gives correct answers so he expects the contestants to give correct answers, too. He is a good fellow so he won't give anyone very big numbers and he always gives one person numbers of same length.

Now you are going to take part in Shapur's contest. See if you are faster and more accurate.

Input

There are two lines in each input. Each of them contains a single number. It is guaranteed that the numbers are made from 0 and 1 only and that their length is same. The numbers may start with 0. The length of each number doesn't exceed 100.

Output

Write one line — the corresponding answer. Do not omit the leading 0s.

#### Sample test(s):

```
input
1010100
0100101
output
1110001
input
000
111
output
111
input
1110
1010
output
0100
input
01110
01100
output
00010
```

#### Code:

```
#逐位比较，相同为1，不同为0
import sys
firstN = sys.stdin.readline().strip()
secondN = sys.stdin.readline().strip()
result = ""
for i in range(len(firstN)):
if firstN[i] != secondN[i]:
result += "1"
else:
result += "0"
print result
```

# 237A Free Cash

Valera runs a 24/7 fast food cafe. He magically learned that next day n people will visit his cafe. For each person we know the arrival time: the i-th person comes exactly at hi hours mi minutes. The cafe spends less than a minute to serve each client, but if a client comes in and sees that there is no free cash, than he doesn't want to wait and leaves the cafe immediately.

Valera is very greedy, so he wants to serve all n customers next day (and get more profit). However, for that he needs to ensure that at each moment of time the number of working cashes is no less than the number of clients in the cafe.

Help Valera count the minimum number of cashes to work at his cafe next day, so that they can serve all visitors.

Input

The first line contains a single integer n (1 ≤ n ≤ 10**5), that is the number of cafe visitors.

Each of the following n lines has two space-separated integers hi and mi (0 ≤ hi ≤ 23; 0 ≤ mi ≤ 59), representing the time when the i-th person comes into the cafe.

Note that the time is given in the chronological order. All time is given within one 24-hour period.

Output

Print a single integer — the minimum number of cashes, needed to serve all clients next day.

Note

In the first sample it is not enough one cash to serve all clients, because two visitors will come into cafe in 8:10. Therefore, if there will be one cash in cafe, then one customer will be served by it, and another one will not wait and will go away.

In the second sample all visitors will come in different times, so it will be enough one cash.

#### Sample test(s):

```
input
4
8 0
8 10
8 10
8 45
output
2
input
3
0 12
10 11
22 22
output
1
```

#### Code:

```
#该题要求计算出到底有几个收银台才能保证来的顾客第一时间就能服务到
#第一行输入为明天到底要来几个顾客
#第二行输入为顾客分别在几点几分来
#每个顾客的服务时间小于一分钟
#所以实际上就相当于判断同一时间来的顾客最多有多少个
import sys
visitors = int(sys.stdin.readline())
cashes = 1;
lastServedTime = (0,0)
served = 1;
for i in range(visitors):
inputs = sys.stdin.readline().split()
currentServedTime = (inputs[0], inputs[1])
if lastServedTime == currentServedTime:
served += 1
if served > cashes:
cashes += 1
else:
served = 1
lastServedTime = currentServedTime
print cashes
```

# 69A Young Physicist

A guy named Vasya attends the final grade of a high school. One day Vasya decided to watch a match of his favorite hockey team. And, as the boy loves hockey very much, even more than physics, he forgot to do the homework. Specifically, he forgot to complete his physics tasks. Next day the teacher got very angry at Vasya and decided to teach him a lesson. He gave the lazy student a seemingly easy task: You are given an idle body in space and the forces that affect it. The body can be considered as a material point with coordinates (0; 0; 0). Vasya had only to answer whether it is in equilibrium. "Piece of cake" — thought Vasya, we need only to check if the sum of all vectors is equal to 0. So, Vasya began to solve the problem. But later it turned out that there can be lots and lots of these forces, and Vasya can not cope without your help. Help him. Write a program that determines whether a body is idle or is moving by the given vectors of forces.

Input

The first line contains a positive integer n (1 ≤ n ≤ 100), then follow n lines containing three integers each: the xi coordinate, the yi coordinate and the zi coordinate of the force vector, applied to the body ( - 100 ≤ xi, yi, zi ≤ 100).

Output

Print the word "YES" if the body is in equilibrium, or the word "NO" if it is not.

#### Sample test(s):

```
input
3
4 1 7
-2 4 -1
1 -5 -3
output
NO
input
3
3 -1 7
-5 2 -4
2 -1 -3
output
YES
```

#### Code:

```
#所有方向的力如果互相抵消，那么这个物质点就是平衡的
#也就是计算出每个方向的和，如果都为0，则输出YES，否则输出NO
import sys
forces = int(sys.stdin.readline())
(x,y,z) =(0,0,0)
for i in range(forces):
force = sys.stdin.readline().split()
x += int(force[0])
y += int(force[1])
z += int(force[2])
if (x,y,z) == (0,0,0):
print "YES"
else:
print "NO"
```

# 141A Amusing Joke

So, the New Year holidays are over. Santa Claus and his colleagues can take a rest and have guests at last. When two "New Year and Christmas Men" meet, thear assistants cut out of cardboard the letters from the guest's name and the host's name in honor of this event. Then the hung the letters above the main entrance. One night, when everyone went to bed, someone took all the letters of our characters' names. Then he may have shuffled the letters and put them in one pile in front of the door.

The next morning it was impossible to find the culprit who had made the disorder. But everybody wondered whether it is possible to restore the names of the host and his guests from the letters lying at the door? That is, we need to verify that there are no extra letters, and that nobody will need to cut more letters.

Help the "New Year and Christmas Men" and their friends to cope with this problem. You are given both inscriptions that hung over the front door the previous night, and a pile of letters that were found at the front door next morning.

Input

The input file consists of three lines: the first line contains the guest's name, the second line contains the name of the residence host and the third line contains letters in a pile that were found at the door in the morning. All lines are not empty and contain only uppercase Latin letters. The length of each line does not exceed 100.

Output

Print "YES" without the quotes, if the letters in the pile could be permuted to make the names of the "New Year and Christmas Men". Otherwise, print "NO" without the quotes.

Note

In the first sample the letters written in the last line can be used to write the names and there won't be any extra letters left.

In the second sample letter "P" is missing from the pile and there's an extra letter "L".

In the third sample there's an extra letter "L".

#### Sample test(s):

```
input
SANTACLAUS
DEDMOROZ
SANTAMOROZDEDCLAUS
output
YES
input
PAPAINOEL
JOULUPUKKI
JOULNAPAOILELUPUKKI
output
NO
input
BABBONATALE
FATHERCHRISTMAS
BABCHRISTMASBONATALLEFATHER
output
NO
```

#### Code:

```
#简单理解成判断第三行输入是否为第一二行输入字母的组合
#多一个字母少一个字母或者有一个字母不同都输出NO
#反之完全一样则输出YES
import sys
firstS = sys.stdin.readline().strip()
secondS = sys.stdin.readline().strip()
thirdS = sys.stdin.readline().strip()
s = firstS + secondS
#如果第一行和第二行字母的总长度与第三行不等，则直接输出NO
if len(s) != len(thirdS):
print "NO"
else:
for i in range(len(s)):
c = s[i]
flag = False
for j in range(len(thirdS)):
if thirdS[j] == c:
thirdS = thirdS[:j] + thirdS[j+1:]
flag = True #表示找到了这个字母在thirdS中的对应字母
break
if not flag:
print "NO"
break
if flag: print "YES"
```

# 268B Buttons

Manao is trying to open a rather challenging lock. The lock has n buttons on it and to open it, you should press the buttons in a certain order to open the lock. When you push some button, it either stays pressed into the lock (that means that you've guessed correctly and pushed the button that goes next in the sequence), or all pressed buttons return to the initial position. When all buttons are pressed into the lock at once, the lock opens.

Consider an example with three buttons. Let's say that the opening sequence is: {2, 3, 1}. If you first press buttons 1 or 3, the buttons unpress immediately. If you first press button 2, it stays pressed. If you press 1 after 2, all buttons unpress. If you press 3 after 2, buttons 3 and 2 stay pressed. As soon as you've got two pressed buttons, you only need to press button 1 to open the lock.

Manao doesn't know the opening sequence. But he is really smart and he is going to act in the optimal way. Calculate the number of times he's got to push a button in order to open the lock in the worst-case scenario.

Input

A single line contains integer n (1 ≤ n ≤ 2000) — the number of buttons the lock has.

Output

In a single line print the number of times Manao has to push a button in the worst-case scenario.

Note

Consider the first test sample. Manao can fail his first push and push the wrong button. In this case he will already be able to guess the right one with his second push. And his third push will push the second right button. Thus, in the worst-case scenario he will only need 3 pushes.

#### Sample test(s):

```
input
2
output
3
input
3
output
7
```

#### Code:

```
#这道题主要是需要推导出相应的数学公式...
#锁上有n个按键，按对，继续按下一个，按错则弹起，需要重新按
#最坏情况下需要按多少次按键才可以把锁打开
import sys
n = int(sys.stdin.readline())
total = 0
for i in range(n, 0, -1):
total += i + (n-i)*(i-1)
print total
```

# 58A Chat room

Vasya has recently learned to type and log on to the Internet. He immediately entered a chat room and decided to say hello to everybody. Vasya typed the word s. It is considered that Vasya managed to say hello if several letters can be deleted from the typed word so that it resulted in the word "hello". For example, if Vasya types the word "ahhellllloou", it will be considered that he said hello, and if he types "hlelo", it will be considered that Vasya got misunderstood and he didn't manage to say hello. Determine whether Vasya managed to say hello by the given word s.

Input

The first and only line contains the word s, which Vasya typed. This word consisits of small Latin letters, its length is no less that 1 and no more than 100 letters.

Output

If Vasya managed to say hello, print "YES", otherwise print "NO".

#### Sample test(s):

```
input
ahhellllloou
output
YES
input
hlelo
output
NO
```

#### Code:

```
#这道题判断给定的输入字符串，如果删掉一些字母是否可以变成hello
#按顺序去找就好了==！
import sys
inputs = sys.stdin.readline().strip()
word = "hello"
for i in range(len(inputs)):
if word == "": break
if inputs[i] == word[0]:
word = word[1:]
if word == "":
print "YES"
else:
print "NO"
```

# 155A I love %username%

Vasya adores sport programming. He can't write programs but he loves to watch the contests' progress. Vasya even has a favorite coder and Vasya pays special attention to him.

One day Vasya decided to collect the results of all contests where his favorite coder participated and track the progress of his coolness. For each contest where this coder participated, he wrote out a single non-negative number — the number of points his favorite coder earned in the contest. Vasya wrote out the points for the contest in the order, in which the contests run (naturally, no two contests ran simultaneously).

Vasya considers a coder's performance in a contest amazing in two situations: he can break either his best or his worst performance record. First, it is amazing if during the contest the coder earns strictly more points that he earned on each past contest. Second, it is amazing if during the contest the coder earns strictly less points that he earned on each past contest. A coder's first contest isn't considered amazing. Now he wants to count the number of amazing performances the coder had throughout his whole history of participating in contests. But the list of earned points turned out long and Vasya can't code... That's why he asks you to help him.

Input

The first line contains the single integer n (1 ≤ n ≤ 1000) — the number of contests where the coder participated.

The next line contains n space-separated non-negative integer numbers — they are the points which the coder has earned. The points are given in the chronological order. All points do not exceed 10000.

Output

Print the single number — the number of amazing performances the coder has had during his whole history of participating in the contests.

Note

In the first sample the performances number 2 and 3 are amazing.

In the second sample the performances number 2, 4, 9 and 10 are amazing.

#### Sample test(s):

```
input
5
100 50 200 150 200
output
2
input
10
4664 6496 5814 7010 5762 5736 6944 4850 3698 7242
output
4
```

#### Code:

```
#这道题用来求都有哪些成绩比之前的成绩都要高或者都要低
#比如第二个例子中 2, 4, 9 and 10的成绩就比之前的成绩高或者低
import sys
contestN = int(sys.stdin.readline())
scores = sys.stdin.readline().split()
result = 0
#定义一个最高成绩，一个最低成绩
maxScore = int(scores[0])
minScore = int(scores[0])
#从头开始判断每次的成绩
#如果比之前的最高成绩高，或者最低成绩低，那么result加1
for i in range(1,contestN):
score = int(scores[i])
if(score > maxScore):
maxScore = score
result += 1
elif(score < minScore):
minScore = score
result += 1
print result
```

# 118B Present from Lena

Vasya's birthday is approaching and Lena decided to sew a patterned handkerchief to him as a present. Lena chose digits from 0 to n as the pattern. The digits will form a rhombus. The largest digit n should be located in the centre. The digits should decrease as they approach the edges. For example, for n = 5 the handkerchief pattern should look like that:

0

0 1 0

0 1 2 1 0

0 1 2 3 2 1 0

0 1 2 3 4 3 2 1 0

0 1 2 3 4 5 4 3 2 1 0

0 1 2 3 4 3 2 1 0

0 1 2 3 2 1 0

0 1 2 1 0

0 1 0

0

Your task is to determine the way the handkerchief will look like by the given n.

Input

The first line contains the single integer n (2 ≤ n ≤ 9).

Output

Print a picture for the given n. You should strictly observe the number of spaces before the first digit on each line. Every two adjacent digits in the same line should be separated by exactly one space. There should be no spaces after the last digit at the end of each line.

#### Sample test(s):

```
input
2
output
0
0 1 0
0 1 2 1 0
0 1 0
0
input
3
output
0
0 1 0
0 1 2 1 0
0 1 2 3 2 1 0
0 1 2 1 0
0 1 0
0
```

#### Code:

```
#这道题根据要求输出一个数字图形..看例子应该很容易理解。
#我的做法就是两次循环分别把上中间行上面和下面的分别进行输出
import sys
n = int(sys.stdin.readline())
for i in range(n):
outputs = ' '*(n-i)*2
if i == 0:
print outputs + "0"
continue
for j in range(i):
outputs += str(j) + " "
outputs += str(i)
for j in range(i-1,-1,-1):
outputs += " " + str(j)
print outputs
for i in range(n,-1,-1):
outputs = ' '*(n-i)*2
if i == 0:
print outputs + "0"
continue
for j in range(i):
outputs += str(j) + " "
outputs += str(i)
for j in range(i-1,-1,-1):
outputs += " " + str(j)
print outputs
```

# 208A Dubstep

Vasya works as a DJ in the best Berland nightclub, and he often uses dubstep music in his performance. Recently, he has decided to take a couple of old songs and make dubstep remixes from them.

Let's assume that a song consists of some number of words. To make the dubstep remix of this song, Vasya inserts a certain number of words "WUB" before the first word of the song (the number may be zero), after the last word (the number may be zero), and between words (at least one between any pair of neighbouring words), and then the boy glues together all the words, including "WUB", in one string and plays the song at the club.

For example, a song with words "I AM X" can transform into a dubstep remix as "WUBWUBIWUBAMWUBWUBX" and cannot transform into "WUBWUBIAMWUBX".

Recently, Petya has heard Vasya's new dubstep track, but since he isn't into modern music, he decided to find out what was the initial song that Vasya remixed. Help Petya restore the original song.

Input

The input consists of a single non-empty string, consisting only of uppercase English letters, the string's length doesn't exceed 200 characters. It is guaranteed that before Vasya remixed the song, no word contained substring "WUB" in it; Vasya didn't change the word order. It is also guaranteed that initially the song had at least one word.

Output

Print the words of the initial song that Vasya used to make a dubsteb remix. Separate the words with a space.

Note

In the first sample: "WUBWUBABCWUB" = "WUB" + "WUB" + "ABC" + "WUB". That means that the song originally consisted of a single word "ABC", and all words "WUB" were added by Vasya.

In the second sample Vasya added a single word "WUB" between all neighbouring words, in the beginning and in the end, except for words "ARE" and "THE" — between them Vasya added two "WUB".

#### Sample test(s):

```
input
WUBWUBABCWUB
output
ABC
input
WUBWEWUBAREWUBWUBTHEWUBCHAMPIONSWUBMYWUBFRIENDWUB
output
WE ARE THE CHAMPIONS MY FRIEND
```

#### Code:

```
#简单来说，就是把输入的字符串中的WUB全部替换成空格
#然后做去多余空格处理进行输出
import sys
words = sys.stdin.readline().strip()
while True:
if "WUB" not in words: break
else:
location = words.find("WUB")
words = words[:location] + " " + words[location+3:]
print " ".join(words.split())
```