You are hereProgramming Problems / 2018 AIPO Preliminary Round Problems

2018 AIPO Preliminary Round Problems


By admin - Posted on 18 January 2018

You are strongly encouraged to complete these problems on your own without help or using the Internet. Problems at the National Finals of the competition will be more difficult than these.
 
Your program should not prompt for input from the user. It should read from the standard input (process input line by line from input file or piped input) and output to the standard output (print out), e.g.:
 
$ cat input.txt
one plus three
$ python3 p2.py < input.txt
$ four
$
$ gcc -o p2 p2.c
$ echo 'one plus three' | ./p2
four
$ ./p2 < input.txt
$ four
 

 

P1 - Luke Skywalker

Luke_SkywalkerThe script for the 138th Starwars movie is being written in a Holywood office. They already ran out of ideas for Jedi family relations.

Given the list of characters and relationship you have to write a list of all the possible combinations using the format "NAME, I am your RELATIONSHIP."

Example: given the characters "Luke" and "Han" and the relationships "brother" and "son". We would like to generate the sentences:


Han, I am your brother.
Han, I am your son.
Luke, I am your brother.
Luke, I am your son.

We want to generated every possible combination and print them in lexicographical order.

Input

The first line will contain the names of the characters. First you'll find the integer C representing the number of characters and then C names separated by spaces.

The second line will contain the relationships. First you'll find the integer R representing the number of relationships and then Rrelationships separated by spaces.

The characters and relationships will be single words of at most length 20 characters. There will be at most 10 names and 10 relationships.

Output

Print all the possible combinations of name and relationship sorted lexicographically. Print the names and relationships as provided in the input. That is, if the input has yOdA, you can't print yoda nor Yoda.

Examples

Input example 1

2 Luke Han
2 father brother

Output example 1

Han, I am your brother.
Han, I am your father.
Luke, I am your brother.
Luke, I am your father.

Explanation example 1

Note than we put first the sentences with "brother" because if lexicographically smaller than "father".

Input example 2

1 a
3 mother father toothbrush

Output example 2

a, I am your father.
a, I am your mother.
a, I am your toothbrush.

 

P2 - Calculator

We want to create an inteligent calculator that is able to understand operations written in English rather than numbers.

Our program has to read an operation from the standard input and print the result.

This is our first version of the calculator so it will only be able to perform sums of numbers from 0 to 9.

Examples:

The result of "one plus three" is "four"

The result of "nine plus two" is "eleven"

Input

The operation to compute. It will always have the format "A plus B" where A and B will be number from 0 to 9 written in English.

Output

The result of the operation written in English.

Examples

Input example 1

one plus three

Output example 1

four

Input example 2

nine plus two

Output example 2

eleven

 

P3 - Complementary DNA

DNA HelixA DNA strand is a sequence of the 4 nucleobases: adenine (A), thymine (T), guanine (G) and cytosine (C). For example: A, ATGC, TTTTTTT and CAT are all valid strands.

Each nucleobases has its own complementary base: adenine is the complementary of thymine, cytguanine is the complementary of cosine. The complementaries of the strands above are: T, TACG, AAAAAAA and GTA.

Write a program that given a DNA strand, computes its complementary.

Input

Your program has to read a string from the standard input (keyboard). The string will be composed of the uppercase characters A, T, G and C and will contain at most 20 characters.

Output

Write a single line with the complementary of the input strand.

Examples

Input example 1

CAT

Output example 1

GTA

Input example 2

ATGC

Output example 2

TACG

 

P4 - Cool numbers

James has created his own computer. He doesn't like to follow trends and instead of binary, James' computer work with base 5.

In base 5, the number are written using only the digits 0 to 4. The first few numbers in base 5 are: 0, 1, 2, 3, 4, 10, 11, 12, 13, 14, 20, 21, ...

James selected base 5 because he loves the number 4. For him, the coolest numbers are the ones with the largest number of digits 4. Hence, the number 144 is cooler than 14 and 43 is as cool as 10004.

Given a number n in base 10, you have to find the coolest number in base 5 from the sequence 0, 1, 2, ..., n and print the number of digits 4 it contains.

Input

A single integer in base 10. n will be at most 10000000 (10^6).

Output

Print the number of digits 4 of the coolest number in the sequence 0, ..., n. Remember it has to be in base 5!

Examples

Example input 1

10

Example output 1

1

Explanation example 1

The result is 1 because the coolest numbers from 0 to 10 in base 5 ares 4 and 14.

Example input 2

25

Example output 2

2

Explanation example 2

The coolest number from 0 to 25 is 24 with two digits 4 (in base 5 is 44).

 

P5 - Problemset

AIPO LogoThe AIPO organisation has to select the problems that will appear in each of the contest ("The Problemset"). One import requirement for the problemset is that it should allow us to select the top N programmers that will advance to the next round.

Each problem have certain difficulty level D, a number from 0 to 10^6. Each contestant has certain level of programming expertise E, a number from 0 to 10^6. Contestants will be able to solve problems whose difficulty is not higher than their expertise.

Example: A contest with expertise 5 will be able to solve problems of difficulty 1 to 5 but won't solve problems with difficulty 6 or higher.

Given the difficult of each of the problems in the problemset and the expertise of every contestant. Compute if it's possible to find exact the top N contestants without ties.

Input

The first line will contain an integer N, the number of contestants we want to select (the top-N).

The second line will contain an integer P, the number of problems we have.

The third line will contain P integers, the difficulty of each of the problems.

The forth line will contain an integer C, the number of contestants.

The fifth line will contain C integers, the expertise of each of the contestants.

All the values will be at most 1 million (10^6). N will never be larger than C.

Output

Print yes if the problemset will let us select the top-N contestants. If its not possible print no.

Examples

Input example 1

1
2
5 10
3
5 9 10

Output example 1

yes

Explanation example 1

The first contestant has expertise 5 so he will solve only the first problem. The second contestant will solve the same problem. The third contestant has expertise 10 so she will solve both problems and end up in the first position. There won't be ties in the top-N cut so the answer is yes.

Input example 2

2
2
5 10
3
5 9 10

Output example 2

no

Explanation example 2

The contestants will solve 1, 1 and 2 problems. We want to get the top-2 but we've got a tie in the second position so the answer will be no.

 

P6 - DNA Hairpin

You probably know that 2 complementary DNA strands can be joined to create a double-stranded DNA sequence (the so-called double helix).

When binding two strands of DNA, each base pairs with one base of complementary type. That is, adenines bound thymines, cytosines bound with guanines.

Example: The bases in the DNA sequences CATATTAC and GTATAATG will bound in as follows:

CATATTAC
||||||||
GTATAATG

Sometimes, a single strand may bound with itself! When such a thing happens the binding is not complete and some parts of the stran may remain free. When a part of a strand binds to itself we say we have a DNA hairpin or a stem-loop.

The sequence TCTACTTCTCCCGCCTATCAGAAAGGGGGCGGGAGAAGCCTT could be folded to create the following hairpin.

Your task is to find longest hair pin in a sequence.

Input

The input will be a single line with a string of characters A, T, G and C. The length of the string will be at most 100 characters.

Output

Print the 2 strands of the longest hairpin separated by a single space.

Examples

Input example 1

AGCT

Output example 1

AG CT

Explanation example 1

The strand can be folded in the middle and AG would bind with CT as follows:

AG
||
TC

Note that the second segment is reversed.

Input example 2

TCTACTTCTCCCGCCTATCAGAAAGGGGGCGGGAGAAGCCTT

Output example 2

CTTCTCCCGCC GGCGGGAGAAG

Explanation example 2

This is the DNA strand from the image above.