Daniel wants Shane to create another classroom contest problem. Unfortunately, he's out of ideas, so he decides to create a roller coaster instead.
The roller coaster can be modelled with a string of ups (^
) and downs (v
). Shane defines the fun level of the roller coaster to be the number of downs in the string.
A sequence is additionally defined as a substring of the roller coaster string, where there are ups followed by downs. The size of the sequence is .
Shane would like to create a roller coaster that has a fun level of , using only and exactly sequences. He also determines that people get the most fun when, if the sequence sizes were listed, the list of sequences is both non-increasing and lexicographically smallest, so both these constraints should be satisfied. Can you determine the string that corresponds to his ideal roller coaster?
Note: a list of sequence sizes is lexicographically smaller than another list if the first index where satisfies .
Oh hey... This seems like a nice classroom contest problem!
Constraints
Input Specification
The first and only line of input will contain and space-separated.
Output Specification
Output a strings of ups (^
) and downs (v
), Shane's ideal roller coaster. It can be proven that there is only one ideal roller coaster.
Note that in any case, the size of the output should be no greater than . If this is exceeded, you may recieve an Output Limit Exceeded (OLE) error.
Sample Input 1
3 2
Sample Output 1
^^vv^v
Explanation for Sample Output 1
There are downs, meaning the fun level is . There are two sequences, ^^vv
and ^v
, with sizes and respectively. This is the lexicographically smallest non-increasing order, so the roller coaster is ideal.
Sample Input 2
15 3
Sample Output 2
^^^^^vvvvv^^^^^vvvvv^^^^^vvvvv
Comments