제식 훈련 1

시간 제한1초메모리 제한1024 MB

요약
N열 M오로 d 간격을 두고 정렬한 훈련병 대열에서 세 번 이하의 지시로 1열 1오 훈련병을 (x, y)로 옮기고 간격을 e로 만들거나, 불가능하면 -1을 출력한다.
난이도

보통10점 중 7점

유형
수학, 구현, 시뮬레이션, 기하
정답자
아직 제출이 없습니다

문제

N×MN \times M 명의 훈련병들이 제식 훈련을 위해 연병장에서 NN열 MM오로 정렬해 서 있다. 이때 인접한 훈련병 간의 거리는 dd이고, ii열 jj오에 서 있는 훈련병의 위치는 2차원 좌표평면 상에서 (d(i−1),d(j−1))(d(i-1), d(j-1))이다.

훈육 교관 하늘이는 훈련병들에게 다음과 같은 지시를 내릴 수 있다.

  • ii열 jj오 훈련병 기준, 개인 간격 kk 간격, 좌우로 나란히!

여기서 i,j,ki, j, k는 모두 양의 정수이며, 1≤i≤N,1≤j≤M,1≤k≤1091 \leq i \leq N, 1 \leq j \leq M, 1 \leq k \leq 10^9을 만족해야 한다.

훈련병들은 이 지시를 받으면 대열을 유지한 상태로 인접한 훈련병 간의 거리를 kk로 만든다. 이때 지시의 기준이 된 ii열 jj오 훈련병의 위치는 변하지 않는다.

하늘이의 목표는 33번 이하의 지시를 통해, 처음 (0,0)(0,0)에 있던 11열 11오 훈련병의 위치를 (x,y)(x,y)로 옮기고 인접한 훈련병 간의 간격을 ee로 만드는 것이다.

입력

첫째 줄에 정수 N,M,d,e,x,yN, M, d, e, x, y가 공백을 사이에 두고 주어진다. (2≤N,M≤104,1≤d,e≤104,−104≤x,y≤1042 \leq N, M \leq 10^4, 1 \leq d, e \leq 10^4, -10^4 \leq x, y \leq 10^4)

출력

첫째 줄에 하늘이가 내릴 지시의 개수 kk (0≤k≤30 \leq k \leq 3)를 출력한다.

이어서 kk개의 줄에 각 지시를 출력한다. 각 지시는 세 정수 i,j,ki, j, k로 나타내며, 공백을 사이에 두고 출력한다. (1≤i≤n,1≤j≤m,1≤k≤1091 \leq i \leq n, 1 \leq j \leq m, 1 \leq k \leq 10^9) 이는 다음과 같은 지시를 의미한다.

  • ii열 jj오 훈련병 기준, 개인 간격 kk 간격, 좌우로 나란히!

kk번째 지시 후에는 11열 11오 훈련병의 위치가 (x,y)(x,y)이어야 하며, 인접한 훈련병 간의 간격은 ee이어야 한다.

만약 33번의 지시 안에 목표를 달성하는 것이 불가능하다면 첫째 줄에 −1-1을 출력한다.

예제1

  1. 예제 1

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