302B.md (2185B)
1 Source: https://codeforces.com/problemset/problem/302/B 2 3 B. Eugeny and Play List 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Eugeny loves listening to music. He has *n* songs in his play list. We know that song number *i* has the duration of *t**i* minutes. Eugeny listens to each song, perhaps more than once. He listens to song number *i* *c**i* times. Eugeny's play list is organized as follows: first song number 1 plays *c*1 times, then song number 2 plays *c*2 times, ..., in the end the song number *n* plays *c**n* times. 22 23 Eugeny took a piece of paper and wrote out *m* moments of time when he liked a song. Now for each such moment he wants to know the number of the song that played at that moment. The moment *x* means that Eugeny wants to know which song was playing during the *x*-th minute of his listening to the play list. 24 25 Help Eugeny and calculate the required numbers of songs. 26 27 Input 28 29 The first line contains two integers *n*, *m* (1 ≤ *n*, *m* ≤ 105). The next *n* lines contain pairs of integers. The *i*-th line contains integers *c**i*, *t**i* (1 ≤ *c**i*, *t**i* ≤ 109) — the description of the play list. It is guaranteed that the play list's total duration doesn't exceed 109 . 30 31 The next line contains *m* positive integers *v*1, *v*2, ..., *v**m*, that describe the moments Eugeny has written out. It is guaranteed that there isn't such moment of time *v**i*, when the music doesn't play any longer. It is guaranteed that *v**i* < *v**i* + 1 (*i* < *m*). 32 33 The moment of time *v**i* means that Eugeny wants to know which song was playing during the *v**i*-th munite from the start of listening to the playlist. 34 35 Output 36 37 Print *m* integers — the *i*-th number must equal the number of the song that was playing during the *v**i*-th minute after Eugeny started listening to the play list. 38 39 Examples 40 41 Input 42 43 ``` 44 1 2 45 2 8 46 1 16 47 ``` 48 49 Output 50 51 ``` 52 1 53 1 54 ``` 55 56 Input 57 58 ``` 59 4 9 60 1 2 61 2 1 62 1 1 63 2 2 64 1 2 3 4 5 6 7 8 9 65 ``` 66 67 Output 68 69 ``` 70 1 71 1 72 2 73 2 74 3 75 4 76 4 77 4 78 4 79 ```