Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
В этой задаче вам понадобится генератор случайных чисел, порождающий случайное число в диапазоне от 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^6) — размеры матрицы и количество запросов соответственно.
Вторая строка содержит целые числа 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.
Для отправки решений необходимо выполнить вход.
|