만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

벤더

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

요약
선형 합동 수열의 계수 a, b, c를 정해 n번의 인접한 컵 교환이 공을 위치 r에서 l로 옮기도록 만들고, 불가능하면 Impossible을 출력한다.
난이도

어려움10점 중 8점

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

문제

로봇 벤더는 돈을 벌기 위해 <<돌리고 돌리기>>라는 오락을 열기로 했다. 오락은 다음과 같다. 벤더는 1번부터 kk번 위치에 놓인 똑같은 컵 kk개 중 하나 아래에 공을 숨기고, nn번 재빠르게 어떤 두 컵의 위치를 바꾼 뒤, 지금 공이 어느 컵 아래에 있는지 맞혀 보라고 한다.

벤더는 로봇이므로 정해진 프로그램에 따라 움직인다. 벤더는 정수열 xix_i를 만드는데, x1=cx_1 = c이고 i>1i > 1에 대해 xi=a⋅xi−1+bx_i = a \cdot x_{i-1} + b이다.

ii번째 단계에서 벤더는 (xi mod k)+1(x_i \bmod k) + 1번 위치와 ((xi+1) mod k)+1\left( (x_i + 1) \bmod k \right) + 1번 위치의 컵을 바꾼다.

처음에 로봇은 rr번 위치의 컵 아래에 공을 숨긴다. 벤더는 nn번 교환한 뒤 공이 ll번 위치의 컵 아래에 있기를 원한다.

공이 든 컵이 rr번 위치에서 ll번 위치로 이동하도록 aa, bb, cc를 찾아라.

입력

입력 파일의 유일한 줄에 정수 네 개 nn, kk, rr, ll이 주어진다 (1≤n≤1051 \le n \le 10^5; 2≤k≤102 \le k \le 10; 1≤r,l≤k1 \le r, l \le k).

출력

그런 수가 없으면 출력 파일에 <<Impossible>>이라는 단어 하나를 출력한다. 그렇지 않으면 음이 아닌 정수 세 개 aa, bb, cc를 출력한다. 수는 10001000을 넘지 않아야 한다.

예제3

  1. 예제 1

    입력
    2 3 1 2
    
    예상 출력
    0 0 1
    
  2. 예제 2

    입력
    3 4 2 4
    
    예상 출력
    2 0 1
    
  3. 예제 3

    입력
    10 2 1 2
    
    예상 출력
    Impossible