Seyrek Tablolar#691

Açıklama Editoryal Tartışma

Seyrek Tablolar

2 saniye

128 megabayt

Zor

$n$ tam sayıdan oluşan bir dizi veriliyor. Aşağıdaki biçimdeki sorguları yanıtlayan bir program yazın: $u$ 'dan $v$ 'ye kadar olan aralıkta, her iki uç dâhil, en küçük değeri bulun.

Giriş

İlk satırda üç tam sayı verilir: n, m~(1 \le n \le 10^5, m \le 10^7) ve a_1~(1 \le a_1 < 16714589) — sırasıyla dizideki eleman sayısı, sorgu sayısı ve dizinin ilk elemanı.

İkinci satırda, ilk sorguyu tanımlayan iki tam sayı u_1 ve v_1~(1 \le u_1, v_1 \le n) verilir.

a_2, a_3, \ldots, a_n elemanları aşağıdaki formülle belirlenir:

a_{i+1} = (23 \cdot a_i + 21563) \bmod 16714589

Örneğin, n = 10 ve a_1 = 12345 ise dizi şöyle olacaktır:

a = (12345, 305498, 7048017, 11694653, 1565158, 2591019, 9471233, 570265, 13137658, 1325095)

Sorgular aşağıdaki şekilde üretilir:

u_{i+1} = ((17 \cdot u_i + 751 + ans_i + 2i) \bmod n) + 1 \\ v_{i+1} = ((13 \cdot v_i + 593 + ans_i + 5i) \bmod n) + 1

Burada ans_i, $i$ -inci sorgunun cevabını gösterir.

Çıktı

u_m, v_m ve ans_m değerlerini — son sorgunun parametrelerini ve cevabını — yazdırın.

Örnekler

Örnek 1

Loading

Loading

n, m (1 \leq n \leq 1 0^{5}, m \leq 1 0^{7})

a_{1} (1 \leq a_{1} < 16714589)

u_{1}

v_{1} (1 \leq u_{1}, v_{1} \leq n)

a_{2}, a_{3}, \dots, a_{n}

a_{i + 1} = (23 \cdot a_{i} + 21563) mod 16714589

n = 10

a_{1} = 12345

a = (12345, 305498, 7048017, 11694653, 1565158, 2591019, 9471233, 570265, 13137658, 1325095)

u_{i + 1} = ((17 \cdot u_{i} + 751 + an s_{i} + 2 i) mod n) + 1 v_{i + 1} = ((13 \cdot v_{i} + 593 + an s_{i} + 5 i) mod n) + 1

an s_{i}

u_{m}, v_{m}

an s_{m}