Задача Segtree2k17. В середовищі крутих олімпіадних гуру модно знати напам’ять розв'яок такої задачі: Дано масив з N чисел та M запитів виду L R. На кожен такий запит потрібно вивести добуток елементів масиву, що мають індекси від L до R, включно. Оскільки, добуток може бути дуже великим, вам потрібно виводити відповідь по модулю.
Розглянемо таку модифікацію цієї задачі: Умова задачі не змінюється, але змінено обмеження:
Оскільки, в такому випадку вхідний файл буде дуже великим, його пропонується генерувати. Код генератора (С++) повинен бути вбудований в розв’язок. (Аналогічний код мовами Pascal та Python 2* , 3* можна завантажити тут).
const int MAXN = 1000 * 1000;
long long a[MAXN];
long long mod;
unsigned s;
unsigned getNext(){
s ^= (s << 13);
s ^= (s >> 17);
s ^= (s << 5);
return s;
}
int main() {
unsigned n, m, seed ;
cin >> n >> m >> mod >> seed;
s = seed;
for(int i = 0; i < n; i++){
a[i] = getNext();
}
long long ans = 0;
for(int i = 0; i < m; i++){
unsigned left = getNext() % n;
unsigned right = getNext() % n;
if(left > right) swap(left, right);
long long result = query(left, right);
ans = (ans + result) % mod;
}
}
Таким чином , вхідними даними будуть N, M, Mod, Seed, де Seed – початкове значення для генератора. У відповідь потрібно вивести суму відповідей на кожен запит (по модулю)
Технічні умови. Програма Segtree2k17 (яка містить вбудований код генератора!) читає з пристрою стандартного введення натуральні числа N, M, Mod, Seed ( 
seed<=232) Програма виводить до пристрою стандартного виведення єдине число – суму результатів (по модулю) на всіх запитах.
Приклади
Введення Виведен
10 15 1000000007 1 216091399
Введення Виведення
5000 100000 1283189389247 8932 541836623127
Введення Виведення
1000 100 100007 7632 47019