Deadlock Detection

In concurrent processing environments, a deadlock is an undesirable situation where two or more threads are mutually waiting for others to finish using some resources and cannot proceed further. Your task is to detect whether there is any possibility of deadlocks when multiple threads try to execute a given instruction sequence concurrently.

The instruction sequence consists of characters 'u' or digits from '0' to '9', and each of them represents one instruction. 10 threads are trying to execute the same single instruction sequence. Each thread starts its execution from the beginning of the sequence and continues in the given order, until all the instructions are executed.

There are 10 shared resources called locks from L0 to L9. A digit k is the instruction for acquiring the lock Lk. After one of the threads acquires a lock Lk, it is kept by the thread until it is released by the instruction 'u'. While a lock is kept, none of the threads, including one already acquired it, cannot newly acquire the same lock Lk.

Precisely speaking, the following steps are repeated until all threads finish.

1. One thread that has not finished yet is chosen arbitrarily.
2. The chosen thread tries to execute the next instruction that is not executed yet.
* If the next instruction is a digit k and the lock Lk is not kept by any thread, the thread executes the instruction k and acquires Lk.
* If the next instruction is a digit k and the lock Lk is already kept by some thread, the instruction k is not executed.
* If the next instruction is 'u', the instruction is executed and all the locks currently kept by the thread are released.



After executing several steps, sometimes, it falls into the situation that the next instructions of all unfinished threads are for acquiring already kept locks. Once such a situation happens, no instruction will ever be executed no matter which thread is chosen. This situation is called a deadlock.

There are instruction sequences for which threads can never reach a deadlock regardless of the execution order. Such instruction sequences are called safe. Otherwise, in other words, if there exists one or more execution orders that lead to a deadlock, the execution sequence is called unsafe. Your task is to write a program that tells whether the given instruction sequence is safe or unsafe.

Input

The input consists of at most 50 datasets, each in the following format.

> n
>  s
>

n is the length of the instruction sequence and s is a string representing the sequence. n is a positive integer not exceeding 10,000. Each character of s is either a digit ('0' to '9') or 'u', and s always ends with 'u'.

The end of the input is indicated by a line with a zero.

Output

For each dataset, if the given instruction sequence is safe, then print "SAFE" in a line. If it is unsafe, then print "UNSAFE" in a line.

Sample Input


11
01u12u0123u
6
01u10u
8
201u210u
9
01u12u20u
3
77u
12
9u8u845u954u
0


Output for the Sample Input


SAFE
UNSAFE
SAFE
UNSAFE
UNSAFE
UNSAFE


The second input "01u10u" may possibly cause a deadlock. After one thread has executed the initial four instructions "01u1", the thread keeps only one lock L1. If another thread executes the first instruction '0' at this time, this thread acquires L0. Then, the first thread tries to acquire L0, already kept by the second thread, while the second thread tries to acquire L1, kept by the first thread; This leads to a deadlock.

<image> -> <image> -> <image>
Figure 1: Why the Sample Input 2 "01u10u" is unsafe.

Contrarily, the third input "201u210u" is safe. If one thread had executed up to "201u21" and another to "20", then one may think it would lead to a deadlock, but this can never happen because no two threads can simultaneously keep L2.





Example

Input

11
01u12u0123u
6
01u10u
8
201u210u
9
01u12u20u
3
77u
12
9u8u845u954u
0


Output

SAFE
UNSAFE
SAFE
UNSAFE
UNSAFE
UNSAFE
#include <iostream>
#include <string>
#include <algorithm>
#define rep(i, n) for(i = 0; i < (n); i++)
using namespace std;

int n;
string s;
bool dp[1024][1025];	//dp[S][T] = (ロック資源の集合がS, 待ち資源の集合がT)になることがあるか

bool solve() {
	int i, j, k, l;
	
	int locked = 0, waiting = 0;
	rep(i, s.length()) {
		if ('0' <= s[i] && s[i] <= '9') {
			waiting = s[i] - '0';
			dp[locked][1 << waiting] = true;
			locked = locked + (1 << waiting);
		}
		else {
			waiting = 10;	//T is covered Sが常に偽になる設定.
			dp[locked][1 << waiting] = true;
			locked = 0;
		}
	}
	
	rep(i, 1024) {
		//iと排反なnumberを探す.
		int digit[10]; int dNum = 0;
		rep(k, 10) {
			if ((i >> k) % 2 == 0) {
				digit[dNum++] = k;
			}
		}
		
		rep(j, 1025) {
			if (!dp[i][j]) continue;
			if ((i | j) == i) return true;
			
			rep(k, 1<<dNum) {
				int locked = 0;
				rep(l, dNum) if ((k >> l) & 1) locked += (1 << digit[l]);
				//waiting = 2^0, 2^1, …, 2^10
				rep(l, 11) {
					if (dp[locked][1 << l]) {
						dp[i | locked][min(1024, j | (1 << l))] = true;	//範囲外参照に注意！
					}
				}
			}
		}
	}
	
	rep(i, 1024) {
		rep(j, 1025) {
			if (!dp[i][j]) continue;
			if ((i | j) == i) return true;	//UNSAFE
		}
	}
	return false;
}

int main() {
	int i, j;
	
	while (cin >> n) {
		if (!n) break;
		cin >> s;
		rep(i, 1024) rep(j, 1025) dp[i][j] = false;
		bool res = solve();
		if (res) cout << "UNSAFE" << endl;
		else cout << "SAFE" << endl;
	}
	return 0;
}

//ポイント：
//・2段がまえの論理。
//・「全体集合から、ありえる状態集合を抽出☆」→「ありえる状態集合から、デッドロックが起きるものを抽出★」
//・「初期状態から「ある状態」に至れるか」の判定を直接的にできるのが、この問題のポイント。
//・「初期状態から「デッドロックが起きる状態」に至れるか」を直接判定しようとすると、再帰を考えることになり、このアプローチでは高速化を大して望めない。
//
//自分用解説：
//「各kについて、スレッドkで命令がa_k個処理された状態」になりえるかは、容易に求まる。（現在ロックしている資源がかぶっていないかを判定するだけ）
//なりえる状態のうち、(次確保したい資源の集合)が(ロックした資源の集合)の部分集合になるものでは、デッドロックが起きる。
//そういうものがない場合は、デッドロックは決して起きない。
//
//{a_1,…,a_10}をすべて試すとO(10000^10)くらいになり間に合わない。a_1, a_2, …の順で決めていくと考えると、わざわざ{a_k}を直接持たなくて良いことに気付く。
//なぜかというと、可能な{a_[i+1], …, a_10}の組み合わせは、
//・現在i個のスレッドのカーソルを確定させた。現在ロックしている資源はS
//という情報から定まり、
//デッドロックの判定は、この情報に
//・確保したい資源はT
//という情報を追加すればできるからである。よって、{a}の情報を持たずに探索ができる。(典型的なDP
//さらに、もう少し考えるとT - S(次確保「できる」資源の集合)を保存することでもデッドロックの判定ができるので、
//・i, S, T - S
//を使ってDPできることが分かる。
//
//また、この探索において、a_iの値を決めることは、「スレッドiでロックしている資源s_i, ロックしたい資源t_iを確定させる」
//ことに他ならないため、a_iを試す代わりに(s_i, t_i)組を試してもよい。
//しかし今回は文字列の長さがそこまで長くないため、直接a_iの値を試せばよい。(10000 < 2^10 * 10なので、上記の工夫はあまり意味がない)
//
//計算量は、(S, T - S)の組み合わせが3^10通り, iが11通り, 遷移が高々n(<=10000)通りより、3^10 * 11 * nくらいになる。
//…あれ、間に合わない。
//
//
//自分用解説2:
//デッドロックは、次欲しい資源がすべてロックされていることである。
//ロックされている資源の集合をS, 次欲しい資源の集合をTとして、ありえる(S, T)の組み合わせを列挙することを考える。(☆)
//1スレッドのとき、ありえる(S, T)の組み合わせは簡単に求まる。その集合を{(s_i, t_i), 1≦i≦hoge}とおく。
//2スレッドのときは、すでにロックしている資源をロックしなければよく、命令列も全スレッド共通なので、
//・(s_i or s_j, t_i or t_j) (s_i and s_j = empty)
//を列挙すればいいことに気付く。
//3スレッドのときも同様。
//今回の問題は、資源の個数≦スレッドの数より、スレッドの数に限りがないと考えてよく、
//ありえる(S, T)について、(S or s_i, T or t_i) (S and s_i = empty)を更新が止まるまでやればいいことが分かる。
//↑はS or s_iがSやs_iを含むことから、Sを2進数で表し、S=0,1,2,…の順で更新していけばいいことが分かる。
//
//一見, hoge=n, Sが2^10通り, Tが2^10通りで、2^20 * 10000 = 100億で間に合わないように見えるが、S and s_i = emptyとなるiだけを列挙すると、
//間に合う。計算量解析：1がk個立っているSはcomb[10][k]通り. そのSについて、S and s_i = emptyなるs_iは2^(10-k)通り. Tは2^10通り. t_iは高々11通り.
//Σcomb[10][k] * 2^(10 - k) = 3^10より、計算量は3^10 * 2^10 * 11 ≒ 6.6 * 10^8となる。(ダメやんけ)
//
//余談：
//☆で「スレッドのカーソルの位置」を列挙したくなりがちだが、デッドロックの条件から、(S, T)の組み合わせを列挙する方が後々筋が良い。
//「列挙するもの」は必ずしも「愚直な全探索」と同一にしなくても良いので、都合の良いものを列挙しよう。

