Mirror Maze

시간 제한2초메모리 제한2048 MB

요약
각 질의 (k, d)마다 k번째 반사가 d미터 거리에 보이도록 1 이상 10^9 이하의 정수 거리 x, y를 찾고, 불가능하면 impossible을 출력한다.
난이도

보통10점 중 6점

유형
수학, 정수론, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

George's birthday is coming up, and his friends are excitedly planning his birthday party. They have already bought his presents and are now planning out the location for the party. After some deliberation, they have decided to host George's party in a mirror maze. Each section of the mirror maze consists of two parallel walls facing each other on which mirrors are placed. This creates the effect of seeing infinite reflections of oneself if you look at one of the walls.

George's friends did some research on how to build mirror mazes, and they discovered that a section of a mirror maze is fun only if the kk-th reflection of the viewer appears dd meters away when the viewer looks at one of the mirrors. George's friends feel confident that they can now build the mirror maze, but they need help figuring out where to put the mirrors so that George will have the most fun. They are planning on building nn sections of the maze, and they know when George enters a section of the maze he will be looking to the left. For each section of the maze, they will build a mirror xx meters to the left of where George will be and yy meters to the right. Because of construction constraints, the distances xx and yy must be integers between 11 and 10910^9. Help George's friends figure out where to place the mirrors for each section such that the kk-th reflection is dd meters away or determine it is impossible to place the mirrors to construct a fun section.

입력

The first line of input is nn (1≤n≤1051 \leq n \leq 10^5), the number of sections in the maze.

Each of the next nn lines will consist of two numbers kk and dd (1≤k,d≤1091 \leq k,d \leq 10^9), where dd is the distance in meters where the kk-th reflection should appear.

출력

Output nn lines, one for each section of the maze. For each section, output two numbers, xx and yy, the left and right distances of the mirrors, or "impossible" (without quotes) if no combination of left and right distances will result in the kk-th reflection appearing dd meters away.

There may be more than 11 pair of xx and yy that satisfy the constraints, you may print any such pair as long as 1≤x,y≤1091 \leq x,y \leq 10^9. It can be shown that if it is possible to place mirrors to create a fun section then there is a pair xx and yy such that 1≤x,y≤1091 \leq x,y \leq 10^9 which creates a fun section.

예제1

  1. 예제 1

    입력
    4
    1 6
    3 16
    2 5
    2 10
    
    예상 출력
    3 1
    1 6
    impossible
    2 3