Little Petya likes permutations a lot. Recently his mom has presented him permutation q 1 , q 2 , ..., q n of length n . A permutation a of length n is a sequence of integers a 1 , a 2 , ..., 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. Let's assume that the board contains permutation p 1 , p 2 , ..., p n at the given moment. Then Petya removes the written permutation p from the board and writes another one instead: p q 1 , p q 2 , ..., p q n . In other words, Petya applies permutation q (which he has got from his mother) to permutation p . All actions are similar to point 1, except that Petya writes permutation t on the board, such that: t q i = p i for all i from 1 to n . In other words, Petya applies a permutation that is inverse to q to permutation p . Let's assume that the board contains permutation p 1 , p 2 , ..., p n at the given moment. Then Petya removes the written permutation p from the board and writes another one instead: p q 1 , p q 2 , ..., p q n . In other words, Petya applies permutation q (which he has got from his mother) to permutation p . All actions are similar to point 1, except that Petya writes permutation t on the board, such that: t q i = 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 1 , s 2 , ..., s n . Besides, we know that throughout