Little Petya likes permutations a lot. Recently his mom has presented him permutation q₁, q₂, ..., q_n of length n.

A permutation a of length n is a sequence of integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ n), all integers there are distinct.

There is only one thing Petya likes more than permutations: playing with little Masha. As it turns out, Masha also has a permutation of length n. Petya decided to get the same permutation, whatever the cost may be. For that, he devised a game with the following rules:

• Before the beginning of the game Petya writes permutation 1, 2, ..., n on the blackboard. After that Petya makes exactly k moves, which are described below.
• During a move Petya tosses a coin. If the coin shows heads, he performs point 1, if the coin shows tails, he performs point 2.
  1. Let's assume that the board contains permutation p₁, p₂, ..., p_n at the given moment. Then Petya removes the written permutation p from the board and writes another one instead: p_q1, p_q2, ..., p_qn. In other words, Petya applies permutation q (which he has got from his mother) to permutation p.
  2. All actions are similar to point 1, except that Petya writes permutation t on the board, such that: t_qi = p_i for all i from 1 to n. In other words, Petya applies a permutation that is inverse to q to permutation p.

We know that after the k-th move the board contained Masha's permutation s₁, s₂, ..., s_n. Besides, we know that throughout the game process Masha's permutation never occurred on the board before the k-th move. Note that the game has exactly k moves, that is, throughout the game the coin was tossed exactly k times.

Your task is to determine whether the described situation is possible or else state that Petya was mistaken somewhere. See samples and notes to them for a better understanding.