돌멩이 배치

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

요약
원형으로 놓인 N개 칸에 돌멩이를 0개 또는 1개씩 놓아, 연속한 K개 칸의 돌멩이 합이 항상 L 이상 R 이하가 되게 배치하거나 불가능을 판정한다.
난이도

보통10점 중 7점

유형
그리디, 슬라이딩 윈도우, 구현
정답자
아직 제출이 없습니다

문제

NN개의 칸이 원형으로 배치되어있고 시계 방향으로 00부터 N−1N-1까지의 번호가 붙어있다. 각 칸에는 돌멩이를 최대 1개까지 놓을 수 있다. 0≤i<N0\leq i < N인 모든 정수 ii에 대해 s_is\_i를 i mod N,(i+1) mod N,(i+2) mod N,⋯ ,(i+K−1) mod Ni \bmod N, (i+1) \bmod N, (i+2) \bmod N, \cdots , (i+K-1) \bmod N번 칸에 있는 돌멩이들의 총 개수라고 정의하자.

0≤i≤N−10 \leq i \leq N-1인 모든 ii에 대해 L≤s_i≤RL \leq s\_i \leq R을 만족하도록 돌멩이를 배치하는 방법을 찾아보자. 불가능하다면 -1을 출력한다.

입력

첫 번째 줄에 테스트 케이스의 개수 TT가 주어진다. (1≤T≤10 000)(1 \leq T \leq 10\ 000)

각 테스트 케이스마다 NN, KK, LL, RR이 공백으로 구분되어 주어진다. (1≤K<N≤300 000;(1 \leq K < N \leq 300\ 000; 0≤L≤R≤K)0 \leq L \leq R \leq K)

모든 테스트 케이스에서 NN의 합은 300 000300\ 000을 넘지 않는다.

입력되는 모든 수는 정수이다.

출력

각 테스트 케이스마다 불가능하다면 한 줄에 -1을 출력한다.

가능하다면 돌멩이의 배치를 나타내는 NN개의 수를 공백으로 구분하여 출력한다. 각 수는 00 또는 11이여야 하며, ii번째 수는 i−1i-1번 칸에 배치된 돌멩이의 개수를 나타낸다.

예제1

  1. 예제 1

    입력
    3
6 4 2 4
5 3 2 2
2 1 0 1
    예상 출력
    1 0 1 0 1 0
-1
0 0