시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6 1 1 16.667%

문제

Due to the snowstorm, you and your family are cold, hungry, and miserable. To make things worse, you have no electricity and can’t drive anywhere. Fortunately, you found a nearby relief shelter which distributes supplies like food and blankets a few times each day. You’ve noticed that the supplies get distributed in a very particular way, and you’d like to take advantage of this in order to obtain the items that your family needs most.

Specifically, a line of N people forms to receive supplies. The shelter has T different types of supplies and exactly B boxes of each type. The first person in line receives a box of the first type, the second person receives a box of the second type, and so on. When the distributors give out a box of the last type, they start again with the first type. If they reach the end of the line, they begin again with the first person in line, being careful to keep track of which type they had just given out. This process continues until there are no more boxes.

Knowing the single type of supply S that your family needs most, you want to figure out where in line you should stand in order to obtain the second-most boxes of that type. After all, it would look suspicious if you were to always receive the most. Although if there are multiple positions in line which receive the most of that type, then you’re okay with receiving the most, and of those positions you’d like the one closest to the end of the line since it’s easier to get. Same for the case of multiple positions receiving second-most.

입력

The first line is the number K of input data sets, followed by the K data sets, each a single line containing the integers N, T , B, and S. Each integer is at least 1 and at most 100. In addition, N ≥ 2 and S ≤ T .

출력

For each data set, output “Data Set x:” on a line by itself, where x is its number. On the next line, output the position in line at which you should stand. Each data set should be followed by a blank line.

예제 입력

2
4 6 3 5
4 3 6 1

예제 출력

Data Set 1:
3

Data Set 2:
4

힌트