There is a straight snowy road, divided into n blocks. The blocks are numbered from 1 to n from left to right. If one moves from the i-th block to the (i + 1)-th block, he will leave a right footprint on the i-th block. Similarly, if one moves from the i-th block to the (i - 1)-th block, he will leave a left footprint on the i-th block. If there already is a footprint on the i-th block, the new footprint will cover the old one.

At the beginning, there were no footprints. Then polar bear Alice starts from the s-th block, makes a sequence of moves and ends in the t-th block. It is known that Alice never moves outside of the road.

You are given the description of Alice's footprints. Your task is to find a pair of possible values of s, t by looking at the footprints.

The polar bears are going fishing. They plan to sail from (s_x, s_y) to (e_x, e_y). However, the boat can only sail by wind. At each second, the wind blows in one of these directions: east, south, west or north. Assume the boat is currently at (x, y).

• If the wind blows to the east, the boat will move to (x + 1, y).
• If the wind blows to the south, the boat will move to (x, y - 1).
• If the wind blows to the west, the boat will move to (x - 1, y).
• If the wind blows to the north, the boat will move to (x, y + 1).

Alternatively, they can hold the boat by the anchor. In this case, the boat stays at (x, y). Given the wind direction for t seconds, what is the earliest time they sail to (e_x, e_y)?

You are fishing with polar bears Alice and Bob. While waiting for the fish to bite, the polar bears get bored. They come up with a game. First Alice and Bob each writes a 01-string (strings that only contain character "0" and "1") a and b. Then you try to turn a into b using two types of operations:

• Write parity(a) to the end of a. For example, .
• Remove the first character of a. For example, . You cannot perform this operation if a is empty.

You can use as many operations as you want. The problem is, is it possible to turn a into b?

The parity of a 01-string is 1 if there is an odd number of "1"s in the string, and 0 otherwise.

It is known that there are k fish species in the polar ocean, numbered from 1 to k. They are sorted by non-decreasing order of their weight, which is a positive number. Let the weight of the i-th type of fish be w_i, then 0 < w₁ ≤ w₂ ≤ ... ≤ w_k holds.

Polar bears Alice and Bob each have caught some fish, and they are guessing who has the larger sum of weight of the fish he/she's caught. Given the type of the fish they've caught, determine whether it is possible that the fish caught by Alice has a strictly larger total weight than Bob's. In other words, does there exist a sequence of weights w_i (not necessary integers), such that the fish caught by Alice has a strictly larger total weight?

Polar bears like unique arrays — that is, arrays without repeated elements.

You have got a unique array s with length n containing non-negative integers. Since you are good friends with Alice and Bob, you decide to split the array in two. Precisely, you need to construct two arrays a and b that are also of length n, with the following conditions for all i (1 ≤ i ≤ n):

• a_i, b_i are non-negative integers;
• s_i = a_i + b_i .

Ideally, a and b should also be unique arrays. However, life in the Arctic is hard and this is not always possible. Fortunately, Alice and Bob are still happy if their arrays are almost unique. We define an array of length n to be almost unique, if and only if it can be turned into a unique array by removing no more than entries.

For example, the array [1, 2, 1, 3, 2] is almost unique because after removing the first two entries, it becomes [1, 3, 2]. The array [1, 2, 1, 3, 1, 2] is not almost unique because we need to remove at least 3 entries to turn it into a unique array.

So, your task is to split the given unique array s into two almost unique arrays a and b.