Description

一般情况下要表示一个1到n的排列，都是简单的将这个排列里的数一个个列出来。现在我想换种方式来表示一个排列，简称变相排列。规则是这样的：事先会告诉你一个1到n的原排列，你要根据原排列来生成变相排列。在变相排列中，第i个数的值表示的是i这个数在原排列中的位置。如原排列是2，3，4，5，1，则对应的变相排列是5，1，2，3，4。你的任务很简单，就是来判断一个排列的变相排列跟原排列是否一样。

Inputs: 输入包含多组测试数据。

针对每组测试数据，第一行给出一个n（1<=n<=100000），表示排列的大小。

接下来的一行给出n个不同的数，表示原排列。n为0时表示输入结束，输入保证1到n的每个数出现且只出现一次。

Output

针对每组测试数据，给出判定的结果。如果一个排列的变相排列跟原排列一样，输出same，否则输出different。

Sample

Input

3
1 3 2

5
2 3 4 5 1

0

Output

same
different

Source: z_y