|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
В этой задаче вам понадобится генератор случайных чисел, порождающий случайное число в диапазоне от 1 до X. Воспользуйтесь реализацией, приведённой ниже.
| C/C++ | Pascal |
| int getRandom(int b, int c, int x) {
static int r;
r = (b * r + c) & 0xffff;
return 1 + r % x;
}
| function getRandom(b, c, x : longint) : longint;
var r : longint;
begin
r := (b * r + c) and $FFFF;
getRandom := 1 + r mod x;
end;
|
Дана числовая матрица A размера N × M. Строки матрицы нумеруются от 1 до N сверху вниз, столбцы — от 1 до M слева направо.
Требуется обработать Q запросов. Каждый запрос содержит 4 числа Y1, Y2, X1, X2, обозначающие границы некоторой подматрицы A. Ответом на запрос является результат применения операции XOR (исключающее ИЛИ) ко всем элементам указанной подматрицы.
Входные данные
Первая строка содержит целые числа N, M и Q (1 <= N, M <= 1000, 1 <= Q <= 10^8) — размеры матрицы и количество запросов соответственно.
Вторая строка содержит целые числа B и C (0 <= B, C < 2^31) — параметры генератора случайных чисел.
Чтобы получить элементы матрицы A, используйте следующий фрагмент кода:
| C/C++ | Pascal |
| for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = getRandom(b, c, 1000);
| for i := 1 to n do
for j := 1 to m do
a[i][j] := getRandom(b, c, 1000);
|
Чтобы получить параметры запроса, используйте следующий фрагмент кода:
| C/C++ | Pascal |
| for (int i = 0; i < q; i++) {
y1 = getRandom(b, c, n);
y2 = getRandom(b, c, n);
x1 = getRandom(b, c, m);
x2 = getRandom(b, c, m);
// ...
}
| for i := 1 to q do begin
y1 := getRandom(b, c, n);
y2 := getRandom(b, c, n);
x1 := getRandom(b, c, m);
x2 := getRandom(b, c, m);
{ ... }
end;
|
Выходные данные
Выведите единственное целое число — результат применения операции XOR к ответам на все Q запросов.
Примеры
| Входные данные | Выходные данные |
2 2 1
5 23 | 20 |
5 5 3
31 47 | 392 |
Примечание
В первом примере порождается матрица с элементами A11 = 24, A12 = 139, A21 = 714, A22 = 589 и запрос с параметрами Y1 = 2, Y2 = 1, X1 = 2, X2 = 1.
Для отправки решений необходимо выполнить вход.
|