题目描述

你有 $n$ 枚硬币，其中恰好有一枚是假币。假币的重量与其余所有真币不同，但事先不知道它是更轻还是更重。

你有一架天平，可以比较两组硬币的总重量。

请设计一种称量方案，使得无论假币是哪一枚、它比真币轻还是重，都能够确定哪一枚硬币是假币，并使最坏情况下所需的称量次数尽可能少。

你需要按照下面给出的脚本格式输出完整决策过程。

注意：

• **不要输出不可能发生的分支。**例如样例中某次称量不可能平衡，因此没有对应的 case =: 分支；
• 每次称量时，天平左右两边放置的硬币数量必须相同；
• 同一枚硬币不能同时出现在天平两边。

输入格式

输入仅包含一个整数 $n$：

$3\le n\le100$。

输出格式

输出所要求的最优称量脚本。

脚本使用以下形式：

• 第一行：

need X weighings

其中 X 表示最坏情况下所需的最少称量次数。

• 一次称量写作：

weigh a+b+... vs c+d+...

• 某次称量的结果分支写作：

case <:
case =:
case >:

分别表示左盘较轻、两盘平衡、左盘较重。

• 当已经能够确定假币编号时输出：

fake x

• 一次称量的所有可能分支结束后输出：

end

嵌套层级按照样例使用两个空格缩进。

只应描述实际可能发生的结果分支。

样例

4

need 2 weighings
weigh 1 vs 2
case <:
  weigh 1+2 vs 3+4
  case <:
    fake 1
  case >:
    fake 2
  end
case =:
  weigh 1 vs 3
  case =:
    fake 4
  case <:
    fake 3
  case >:
    fake 3
  end
case >:
  weigh 1+2 vs 4+3
  case >:
    fake 1
  case <:
    fake 2
  end
end