eolymp
bolt
Try our new interface for solving problems
Problems

Finding Lines

Finding Lines

Time limit 2 seconds
Memory limit 128 MiB

Annabel and Richard like to invent new games and play against each other. One day Annabel has a new game for Richard. In this game there is a game master and a player. The game master draws n points on a piece of paper. The task for the player is to find a straight line, such that at least p percent of the points lie exactly on that line. Richard and Annabel have very good tools for measurement and drawing. Therefore they can check whether a point lies exactly on a line or not. If the player can find such a line then the player wins. Otherwise the game master wins the game.

There is just one problem. The game master can draw the points in a way such that it is not possible at all to draw a suitable line. They need an independent mechanism to check whether there even exists a line containing at least p percent of the points, i.e. ceil(n * p / 100) points. Now it is up to you to help them and write a program to solve this task.

Input data

Consists of:

  • one line with one integer n (1n10^5), the number of points the game master has drawn;

  • one line with one integer p (20p100), the percentage of points which need to lie on the line;

  • n lines each with two integers x and y (0x, y10^9), the coordinates of a point.

No two points will coincide.

Output data

Output one line containing either "possible" if it is possible to find a suitable line or "impossible" otherwise.

prb7856.gif

Examples

Input example #1
5
55
0 0
10 10
10 0
0 10
3 3
Output example #1
possible
Input example #2
5
45
0 0
10 10
10 0
0 10
3 4
Output example #2
impossible
Source 2014 ACM North Western European Regional Contest (NWERC), Ноябрь 30, Задача F