Channel
Contest: Pinely Round 2 (Div. 1 + Div. 2)
Difficulty rating: 800
Tags: greedy, implementation

Petya is an administrator of a channel in one of the messengers. A total of $$$n$$$ people are subscribed to his channel, and Petya is not considered a subscriber.

Petya has published a new post on the channel. At the moment of the publication, there were $$$a$$$ subscribers online. We assume that every subscriber always reads all posts in the channel if they are online.

After this, Petya starts monitoring the number of subscribers online. He consecutively receives $$$q$$$ notifications of the form "a subscriber went offline" or "a subscriber went online". Petya does not know which exact subscriber goes online or offline. It is guaranteed that such a sequence of notifications could have indeed been received.

Petya wonders if all of his subscribers have read the new post. Help him by determining one of the following:

- it is impossible that all $$$n$$$ subscribers have read the post;
- it is possible that all $$$n$$$ subscribers have read the post;
- it is guaranteed that all $$$n$$$ subscribers have read the post.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$a$$$, and $$$q$$$ ($$$1 \le n \le 100$$$, $$$0 \le a \le n$$$, $$$1 \le q \le 100$$$) — the number of subscribers of the channel, the initial number of subscribers online, and the number of notifications.

The second line of each test case contains a string of length $$$q$$$, consisting of characters '+' and '-'. The $$$i$$$-th of these characters is '+', if the $$$i$$$-th notification tells that a subscriber goes online, and it is '-' otherwise.

Output format:
For each test case, output a single line: "YES" if all $$$n$$$ subscribers are guaranteed to have read the post, "NO" if it is impossible for all $$$n$$$ subscribers to have read the post, and "MAYBE" otherwise.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, there are $$$5$$$ out of $$$5$$$ subscribers online in the very beginning, so they will all read the post no matter what. The answer is "YES".

In the second test case, the number of subscribers online becomes $$$4$$$ after the first two notifications, next someone goes offline, and thus the fifth subscriber has no chance of reading the post. It is impossible for all the subscribers to read the post, so the answer is "NO".

In the third test case, on the one hand, the same person may have gone offline and online (in this case only $$$4$$$ out of $$$5$$$ subscribers have read the post), on the other hand, the last notification may have told that the fifth subscriber has gone online (in this case all subscribers have read the post). We cannot deduce which of the two holds, so the answer is "MAYBE".

In the fourth test case, there have to be five subscribers online after all the notifications. All of them will read the post, so the answer is "YES".

Example input:
4
5 5 3
--+
5 2 3
++-
5 4 2
-+
5 0 7
++++-++

Example output:
YES
NO
MAYBE
YES

Editorial:
Let $$$p$$$ be the total number of + signs in the notification string. If $$$a + p < n$$$, then the answer is clearly "NO".
Now let's look at the current number of users online. Initially there are $$$a$$$ of them. Each notification either increases this number by $$$1$$$, or decreases it by $$$1$$$. If at some moment of time the number of users online is $$$n$$$, then all users are online, thus, everyone must have read the post. The answer is "YES" in this case.
Otherwise the answer is "MAYBE". Indeed, suppose that the number of users online never hits $$$n$$$, but $$$a + p \ge n$$$. On the one hand, if the first $$$(n - a)$$$ notifications of the + type correspond to new users, then all subscribers will have read the post. On the other hand, a situation when the $$$n$$$-th user never log in is also possible.