As common sense tells us, competitive programmers excel at rowing. The olympic lane is a wonderful place to row, run and work out. What few take their time to appreciate are the capybaras that inhabit the region. Capybaras are fascinating animals! Aside from their beauty, they possess many interesting behaviours. Did you know that capybaras can live in packs as big as 100 individuals?
In a pleasant sunny morning, Yan was running, as usual. Watching the capybaras, he noticed that they would line up to sunbath. Each capybara was paired with another one, and only another one. Two capybaras can be paired if and only if both see each other. A capybara sees everything in the direction it is looking.
Curious, Yan decided to represent the capybaras by the letters A and B, where A indicates that the capybara is looking right, and B indicates that the capybara is looking left.
For example, the sequence AABABB accurately represents capybaras sunbathing, because it is possible to pair every capybara according to the rules above. Yan was so fascinate by this that he slipped and felt into the water, messing his representations. He was able to recover some, but now they are all messed up with each other. Can you help him and find out if a given sequence represent capybaras sunbathing?
Every instance contains a sequence S of characters, composed only of 'A' and 'B' – Yan's representation. You may assume that 1 ≤ |S| ≤ 105.
The output should contain a single line. Print "Sim" if the sequence represents capybaras sunbathing, or "Nao" otherwise.
## Input
Every instance contains a sequence S of characters, composed only of 'A' and 'B' – Yan's representation. You may assume that 1 ≤ |S| ≤ 105.
## Output
The output should contain a single line. Print "Sim" if the sequence represents capybaras sunbathing, or "Nao" otherwise.
[samples]
**Definitions**
Let $ M \in \mathbb{Z}^+ $ be the number of places.
Let $ K \in \mathbb{Z}^+ $ be the number of available hours.
Let $ A = (a_1, a_2, \dots, a_M) $ be a sequence of non-negative integers, where $ a_i $ is the initial number of students at place $ i $.
**Constraints**
1. $ 2 \leq M \leq 10^5 $
2. $ 1 \leq K \leq 10^9 $
3. $ 0 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, M\} $
**Objective**
After performing at most $ K $ moves (each move transfers one student from one place to another), minimize the maximum number of students at any single place.
Let $ S = \sum_{i=1}^M a_i $ be the total number of students.
Find the minimum possible value of $ \max_{i} b_i $, where $ B = (b_1, \dots, b_M) $ is a configuration of students such that:
- $ \sum_{i=1}^M b_i = S $,
- $ \sum_{i=1}^M \max(0, a_i - b_i) \leq K $ (i.e., total students moved out ≤ $ K $).
This minimum maximum is:
$$
\left\lceil \frac{S}{M} \right\rceil
$$
if $ K $ is sufficient to redistribute students to within one of the average; otherwise, it is the original maximum minus the maximum possible reduction under $ K $ moves.
But more precisely, the optimal final maximum is:
$$
\min \left\{ x \in \mathbb{Z} \,\middle|\, \sum_{i=1}^M \max(0, a_i - x) \leq K \text{ and } x \geq \left\lceil \frac{S}{M} \right\rceil \right\}
$$
Thus, the answer is the smallest integer $ x $ such that:
$$
\sum_{i=1}^M \max(0, a_i - x) \leq K
$$
This $ x $ is the minimal possible maximum after $ K $ moves.