Marriage Safety Check

Consider n couples, where the male in the i-th couple is denoted by \(B_i\) and the female by \(G_i\). It is known that for any \(i \le j\), \(B_i\) and \(G_j\) have a past relationship (be it in kindergarten, high school, or college). In a twist of fate, if a particular couple, say couple \(i\), faces marital discord and divorces, a chain reaction may occur: for instance, if \(B_i\) and \(G_i\) separate, then \(B_i\) might reunite with \(G_j\) (where \(i \le j\)), which in turn causes trouble for couple \(j\), and so on.

A marriage \(i\) is defined as unsafe if, under the assumption that \(B_i\) and \(G_i\) divorce, all \(2n\) individuals can still be paired into \(n\) couples such that an allowed pair \(\big(B_p,G_q\big)\) satisfies \(p \le q\). Otherwise, marriage \(i\) is considered safe.

Your task is to determine for each couple whether their marriage is safe.

Observation: In the bipartite graph where an edge exists between \(B_p\) and \(G_q\) if and only if \(p \le q\), the only perfect matching is the trivial one: \(B_i\) with \(G_i\) for all \(1 \le i \le n\). Thus, if a divorce forces the pair \((B_i, G_i)\) to break up, there will be no alternative perfect matching. In other words, every marriage is safe.

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le 10^5\)) on the first line, representing the number of couples.

outputFormat

Output \(n\) lines. The i-th line should contain the word Safe if the i-th marriage is safe or Unsafe if it is unsafe. Based on the reasoning, every marriage is safe.

sample

1

Safe