本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1288. D. Wildest Dreams


Description

Secretly, Arup loves Taylor Swift's music. He covers for his addiction by claiming that Anya, his three-year-old daughter, forces him to play the Taylor Swift CD in the car whenever she's in it. The reality is that Arup also listens to the CD even when Anya isn't in the car.

Both of them have peculiar listening habits. Anya typically obsesses over a single song and will request that Arup play that song on infinite repeat while she is in the car. For example, the current song Anya is obsessed with is track 9, Wildest Dreams. So, when Anya enters the car, Arup immediately starts playing track 9 (from the beginning of the track) and this song is played
repeatedly. Arup, however, wants to listen to the whole CD and not just one track repeatedly. So, whenever Anya exits the car, Arup just lets the CD play in its natural ordering (tracks play in order and when the end of the CD is reached, track 1 starts again). If Anya exits the car in the middle of her favorite song playing, Arup just lets it continue to play that track until its end and then advances to the next song. For our example, if Anya exits the car in the middle of track 9, Arup lets track 9 continue until its end and then advance to the next song (track 10 or if track 9 is the end of CD, track 1).



The Problem:
Arup is curious exactly how long he has listened to Anya's favorite song. Given a list of the lengths of each song, when Anya is in the car and the song Anya is obsessed with, calculate the amount of time Arup has to hear the song that Anya is obsessed with. Recall that when Anya enters the car, her song is played from the beginning and the song keeps repeating as long as
Anya is in the car. You may assume that if Anya gets out of the car in the middle of Anya's song playing, Arup will continue listening to it instead of forwarding the CD to the next song but when Anya’s song is finished the next song will continue. If Anya’s song ends exactly when Anya is leaving the car, the next song will continue, i.e., Anya’s song does not loop back to the
beginning.

Since Anya changes which CD she's obsessed with periodically, write a program that can solve multiple instances of the  problem.

Input

The first line of input will contain a single positive integer, n (1 ≤ n ≤ 50), representing the number of CDs Anya has been obsessed with.
The first line of input for each CD will contain two integers: t (1 ≤ t ≤ 20), the number of tracks on the CD, and k (1 ≤ k ≤ t), the track that Anya is obsessed with. The second line of input for each CD contains t space separated positive integers representing the lengths of each of the t tracks on the CD, in order, in seconds. No CD will be more than 86,400 seconds in length. The third line of input for each CD contains a single positive integer, d (1 ≤ d ≤ 100), the number of days to evaluate. The following d lines contain information about each day. Each of these lines  will start with an integer, si (1 ≤ si ≤ 20), the number of segments of driving for day i. This is  followed by si positive integers, representing the lengths of each of the driving segments, in seconds. Assume that Anya is in the car for the odd-number segments (first, third, fifth, etc.) The sum of the lengths of each driving segment will never exceed 86,400, the number of seconds in a day.

Output

At the beginning of each CD, on a single line, output “CD #c:” where c is the CD number (starting with 1). Then, on the following d lines, where d represents the number of days that CD was played, output the number of seconds Arup listed to Anya's favorite song on the CD, for each day, respectively.

Leave a blank line after the output for each CD.

Samples

Input Copy
2
13 9
212 231 231 235 193 219 207 211 220 247 250 195 270
4
3 1000 900 1000
3 10000 10000 10000
1 2000
2 500 600
2 2
100 200
5
1 70
5 300 277 131 10000 58
2 200 50
2 201 50
2 199 50
Output
CD #1:
2100
20780
2000
660

CD #2:
70
7335
200
251
200

Source

UCF2016
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1032. UCF 2016
My history solutions

You didn't submit any solution!
Submit your solution

Login Register