Pranka2009!24!03 Bottles Description

Бутилков конвейер Управителя на фабриката за безалкохолни напитки “Газова наслада” е наистина вманиачен на тема контрол над служителите си. Той не може да допусне във фабриката му да става нещо и той да не знае за него. Последното му желание е да може да контролира количеството бутилки което е произведено от определени негови работници в даден ден. Работниците работят на една поточна линия, като всеки ден всеки работник застава на едно и също място, за това местата служат за нещо като индекси на работниците. Така ако има общо n работника на линията индексите на работниците са 0, 1,..., n- 1. Нашия управител задава множество въпроси от сорта на: “Кажи ми работниците от индекс i1 до индекс i2 колко бутилки са произвели” и тъй като той е много взискателен ние трябва да сме готови да му отговорим и то бързо. Вход В тази задача входа не е даден директно, а вие сами ще трябва да генерирате данните, тъй като те са прекалено обемисти и би отнело прекалено много време да се изчитат всички те. На първия ред на входа седи броя на тестовите примери (различните конфигурации за които би се заинтересувал управителя). След това следва последователност от тестове. На първия ред на всеки тест има записани числата n (n <= 106) и m (m <= 104) – съответно броя на работниците на конвейрната линия и броя на въпросите които управителя смята да зададе. Следващите три реда на входа за всеки тест съдържат данни от които се генерират същинските данни за теста. На втория ред на всеки тест има записани числата x0, a, b и mod (mod <= 101; x0 >= 0, x0 < mod; a, b <= 101) - x0 е броят бутилки които е произвел работника с индекс 0 през деня който ни интересува. След това броят на произведените бутилки от другите работници може да се генерира на следния принцип: xi = (a * xi-1 + b) % mod за i = 1…n-1. Ред три на всеки тестов пример съдържа стойностите y0, c, d (c,d <= 101; y0 >= 0, y0 < n) от който се генерира редицата с m члена y0, y1,…,ym-1 като yi = (c * yi-1 + d) % n за i >= 1. Ред 3 съдържа подобни данни от който може да се генерира редицата zi: z0, e, f (e,f <= 101; z0 >= 0, z0 < n) като zi = (e * zi-1 + f) % n за i = 1…m-1. Тези две редици – yi и zi служат за генериране на въпросите – всъщност всяка една двойка(yi, zi) представлява въпрос – последователно за всички i трябва да определите каква е сумата на произведените бутилки от работници с индекси между yi и zi включително (забележете, че не е задължително yi <= zi). Изход Последователно за всяка двойка на отделен ред на изхода трябва да изведете каква е съответната сума. Пример 1 4 3 1 3

4 2 1 7 1 1 1 2

4 1 3 3

Пояснение: Генерираните редици за x, y и z са съответно: x: 3 0 1 3; y: 1 2 3 0; z: 3 1 3 1