The first place team was from Centennial High School. The team members were David Madsen,  Guhn Chang, Darrell Draney. The second place team was also from Centennial High School. The team members were Nalin Ratnayake, Mike Owen, Mark Goodell. The third team was from Bishop Kelly High School and Sandpoint High School. The team members were Joise Imlay (Sandpoint), Greg Oden and Mike Peller (Bishop Kelly). Six teams finished at least one program correctly.

The Problems

• Problem 1: Anagrams
• Problem 2: Vigenere Code
• Problem 3: Longest Increasing Subsequence

Problem 1: Anagrams

Examples:

Input:
rationalizes
realizations

Output:
rationalizes and realizations are anagrams
 

Input:
stop
stoop

Output:
stop and stoop aren't anagrams
 

Problem 2: Vigenere Code

  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
A a b c d e f g h i j k l m n o p q r s t u v w x y z
B b c d e f g h i j k l m n o p q r s t u v w x y z a
C c d e f g h i j k l m n o p q r s t u v w x y z a b
D d e f g h i j k l m n o p q r s t u v w x y z a b c
... and so on
 

The code word, say ``rose'' is then repeated over and over, above the message you are encoding. For example, suppose you wish to encode the following letters:

 a c a b d

The code word would be placed over the message as shown below.

r o s e r
a c a b d

The code would then require you to run down the column R in the alphabet table until it intersected row A, finding the letter r. You would then run down column O to the intersection of line C, which would give you q, and down S to row A, giving s, and so on for the rest of the message. The encoded message would thus be  r q s f u. Note that if the message contains a non letter, then the non-letter is left unchanged.

Your program would read in two data lines. The first data line contains the code word. The code word will be a single word with 1 to 10 letters. The second data line will contain the message. Your program should print out the coded message (all in lower case).   Note that if the code is longer than the message, then your program should ignore the excess letters in the code word.
 

 Examples:

Input:
rose
The Internet never retreats.

Output:
kvw zbliibwx bwzvf vvhjirhk.

Input:
rose
THIS IS A CODED MESSAGE.

Output:
kvaw wk r ususv dskwruw.

Input:
penguin
I've been there but I didn't do it!

Output:
x'ik jrtr zbmet oan v hvjh'g hb cb!

Problem 3: Longest Monotone Subsequence

Description: A monotone increasing subsequence is a subset of numbers which are strictly increasing from left to right. This definition does not require that the numbers be adjacent or that the longest sequence be unique. For example, in the following sequence:

1, 2, 9, 4, 7, 3, 11, 8, 14, 6

the sequences ``1, 2, 4, 7, 11, 14'' and ``1, 2, 3, 8, 14'' are both monotone increasing subsequence. Write a program that finds the longest
monotone increasing subsequence in a set of integers. In the above example, it is ``1, 2, 4, 7, 11, 14.''

Input Format:
The first line contains the number of integers in the set. The second line contains the integers separated by spaces.  You may assume that there will be no more than 31 integers in the set.

Example:

Input:
10
1 2 9 4 7 3 11 8 14 6

Output:
longest monotone subsequence:  1  2  4  7  11  14