Problem E
Exclusive Equation

You and your friends are preparing for an exciting intellectual challenge this weekend. Each friend selects a number and writes it on multiple pieces of paper. You are given all these pieces of paper, along with a target number. Your task is to determine whether it is possible to produce the target number by combining the given numbers on the pieces of paper using only the exclusive-or (XOR) operator. You may use as many pieces of paper as you like, but only each piece once. Before using any pieces of paper, the current value produced is zero.

The XOR operator is a binary operation that takes two numbers and operates on their binary representations. It performs a logical XOR on each pair of corresponding bits: the result is 1 if the bits are different, and 0 if they are the same. For example, 5 XOR 3 = 6 because:

5 in binary is 101

3 in binary is 011

XOR result is 110, which is 6 in decimal.

Given the numbers on the pieces of paper and the target number, can you determine if the target can be achieved using the XOR operation?

Input

The first line contains two integers $N$ (number of participants) and $T$ (target number). Then follow $N$ lines, each containing an integer $N_i$ (participant’s number) and $K_i$ (number of copies available, $K_i \geq 1$).

Output

Output "possible", if it is possible to produce the target number, otherwise output "impossible".

Limits

• $1 \leq N \leq 35$

• $0 \leq T < 2^{64}$

• $1 \leq N_i < 2^{64}$

• $1 \leq K_i \leq 100$

4 12
1 2
5 2
11 2
8 2

possible

4 12
1 2
5 2
11 2
4 2

impossible