Twilight Sparkle's Magic Spells

twilight-1.md

Twilight Sparkle's Magic Spells

Twilight Sparkle is researching some magic spells. A spell is a non-empty finite sequence of Apples, Bananas, or Ciwifruit.

Spells can be safe or unsafe. An unsafe spell contains one or more of the following patterns:

Pattern	Name
AAAAA	Appleboom
ABBA	Stockholm Syndrome
ABCABC	Double Rainbow

A safe spell contains none of these patterns.

Help Twilight determine whether a spell is safe or unsafe.

Examples

BAAAAAB is unsafe, as it contains an Appleboom.

AAAACA is safe. While it has five Apples, the Ciwifruit in between means that it can't form an Appleboom.

ABBABBA is unsafe, as it contains two (overlapping) Stockholm Syndromes.

ABBAAAAA is also unsafe, as it contains both a Stockholm and an Appleboom. They don't cancel out!

CBACBA is safe. It has the same fruit as a Double Rainbow, but the fruit are in the wrong order.

Input

The first line of input will contain a single integer, 0 < N ≤ 100, representing the length of the spell.

The next line will contain a string of letters, each either A, B, or C. This is the spell itself.

Output

Output SAFE if the spell is safe; otherwise UNSAFE.

Samples

Example 1

Input:

1
A

Output:

SAFE

Example 2

Input:

4
ABBA

Output:

UNSAFE

twilight-2.md

Twilight Sparkle's Magical Research

While experimenting with her spells, Twilight Sparkle noticed something peculiar: she would often end up with more ingredients than she started with.

For example, if she casts the Boulanger spell on u ukeleles and v vuvuzelas, she would end up with 2u + 3v ukeleles and 5u + v vuvuzelas afterward.

This effect can stack: if she casts Boulanger again, she'll have 2(2u + 3v) + 3(5u + v) = 19u + 9v ukeleles and 5(2u + 3v) + (5u + v) = 15u + 16v vuvuzelas.

In general, a spell can transform u ukeleles and v vuvuzelas into Au + Bv ukeleles and Cu + Dv vuvuzelas, where A, B, C, and D are constants specific to the spell.

Help Twilight figure out how many ukeleles and vuvuzelas she would have, given the specification for a spell and the number of times she casts it. (Whether that is a good idea or not is out of scope for this task.)

Input

The first line will contain four space-separated integers, 0 ≤ A, B, C, D < 10⁵, which specify the spell.

The second line will contain one integer, 0 ≤ N < 10⁹. This is the number of times Twilight wants to cast the spell.

Output

Output two space-separated integers: the final number of ukeleles and vuvuzelas, respectively.

As these numbers can be large, you must only output the last 5 digits of each number. For example, if the answer is 987654321, output 54321 instead.

Subtasks

• N ≤ 1000 (25%)
• No restrictions (75%)