# CF1472B - Fair Division

## 题目描述

Alice and Bob received n candies from their parents. Each candy weighs either 1 gram or 2 grams. Now they want to divide all candies among themselves fairly so that the total weight of Alice’s candies is equal to the total weight of Bob’s candies.

Check if they can do that.

Note that candies are not allowed to be cut in half.

## 输入

The first line contains one integer t (1≤t≤10^4^) — the number of test cases. Then t test cases follow.

The first line of each test case contains an integer n (1≤n≤100) — the number of candies that Alice and Bob received.

The next line contains n integers a1,a2,…,an — the weights of the candies. The weight of each candy is either 1 or 2.

It is guaranteed that the sum of n over all test cases does not exceed 10^5^.

## 输出

For each test case, output on a separate line:

“YES”, if all candies can be divided into two sets with the same weight;
“NO” otherwise.
You can output “YES” and “NO” in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).

Input

Output

## 注意

In the first test case, Alice and Bob can each take one candy, then both will have a total weight of 1.

In the second test case, any division will be unfair.

In the third test case, both Alice and Bob can take two candies, one of weight 1 and one of weight 2.

In the fourth test case, it is impossible to divide three identical candies between two people.

In the fifth test case, any division will also be unfair.

# CF1166A - Silent Classroom

## 题目描述

There are n students in the first grade of Nlogonia high school. The principal wishes to split the students into two classrooms (each student must be in exactly one of the classrooms). Two distinct students whose name starts with the same letter will be chatty if they are put in the same classroom (because they must have a lot in common). Let x be the number of such pairs of students in a split. Pairs (a,b) and (b,a) are the same and counted only once.

For example, if there are 6 students: “olivia”, “jacob”, “tanya”, “jack”, “oliver” and “jessica”, then:

• splitting into two classrooms (“jack”, “jacob”, “jessica”, “tanya”) and (“olivia”, “oliver”) will give x=4 (3 chatting pairs in the first classroom, 1 chatting pair in the second classroom),
• splitting into two classrooms (“jack”, “tanya”, “olivia”) and (“jessica”, “oliver”, “jacob”) will give x=1 (0 chatting pairs in the first classroom, 1 chatting pair in the second classroom).

You are given the list of the n names. What is the minimum x we can obtain by splitting the students into classrooms?

Note that it is valid to place all of the students in one of the classrooms, leaving the other one empty.

## 输入

The first line contains a single integer n (1≤n≤100) — the number of students.

After this n lines follow.

The i-th line contains the name of the i-th student.

It is guaranteed each name is a string of lowercase English letters of length at most 20. Note that multiple students may share the same name.

## 输出

The output must consist of a single integer x — the minimum possible number of chatty pairs.

Input

Output

Input

Output

Input

Output

## 注意

In the first sample the minimum number of pairs is 1. This can be achieved, for example, by putting everyone except jose in one classroom, and jose in the other, so jorge and jerry form the only chatty pair.

In the second sample the minimum number of pairs is 2. This can be achieved, for example, by putting kambei, gorobei, shichiroji and kyuzo in one room and putting heihachi, katsushiro and kikuchiyo in the other room. In this case the two pairs are kambei and kyuzo, and katsushiro and kikuchiyo.

In the third sample the minimum number of pairs is 4. This can be achieved by placing three of the students named mike in one classroom and the other two students in another classroom. Thus there will be three chatty pairs in one classroom and one chatty pair in the other classroom.

# CF1166B - All the Vowels Please

## 题目描述

Tom loves vowels, and he likes long words with many vowels. His favorite words are vowelly words. We say a word of length k is vowelly if there are positive integers n and mm such that n⋅m=k and when the word is written by using n rows and mm columns (the first row is filled first, then the second and so on, with each row filled from left to right), every vowel of the English alphabet appears at least once in every row and every column.

You are given an integer k and you must either print a vowelly word of length k or print −1 if no such word exists.

In this problem the vowels of the English alphabet are ‘a’, ‘e’, ‘i’, ‘o’ ,’u’.

## 输入

Input consists of a single line containing the integer k (1≤k≤10^4^) — the required length.

## 输出

The output must consist of a single line, consisting of a vowelly word of length k consisting of lowercase English letters if it exists or −1 if it does not.

If there are multiple possible words, you may output any of them.

Input

Output

Input

Output

## 注意

In the second example, the word “agoeuioaeiruuimaeoieauoweouoiaouimae” can be arranged into the following 6×6 grid: It is easy to verify that every row and every column contain all the vowels.