Make a Roller Coaster

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

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 k ups followed by k downs. The size of the sequence is k.

Shane would like to create a roller coaster that has a fun level of N, using only and exactly M 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 S is lexicographically smaller than another list T if the first index where S_i \ne T_i satisfies S_i < T_i.

Oh hey... This seems like a nice classroom contest problem!

Constraints

1 \le M \le N \le 10^5

Input Specification

The first and only line of input will contain N and M 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 2 \times 10^5. 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 3 downs, meaning the fun level is 3. There are two sequences, ^^vv and ^v, with sizes 2 and 1 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

There are no comments at the moment.