- Time limit: 1.00 s
- Memory limit: 512 MB
Tien varrella on n rakennusta, jotka on numeroitu 1,2,\ldots,n. Jokaisen rakennuksen alakerrassa on pizzeria ja yläkerrassa on asuinhuoneisto.
Pizzan hinta rakennuksen k pizzeriassa on p_k, ja pizzan tilaaminen rakennuksen a pizzeriasta rakennuksen b huoneistoon maksaa p_a+|a-b|.
Tehtäväsi on käsitellä seuraavia kyselyitä:
- rakennuksen k pizzan hinnaksi tulee x
- mikä on halvin hinta pizzalle, joka tilataan rakennukseen k?
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja q: rakennusten määrä ja kyselyiden määrä.
Seuraavalla rivillä on n kokonaislukua p_1,p_2,\ldots,p_n: pizzan hinta kussakin rakennuksessa aloitustilanteessa.
Lopuksi syötteessä on q riviä, jotka kuvaavat kyselyt. Jokainen rivi on muotoa "1 k x" tai "2 k".
Tuloste
Tulosta vastaus jokaiseen tyypin 2 kyselyyn.
Esimerkki
Syöte:
4 3 4 2 3 2 2 1 1 1 1 2 1
Tuloste:
3 1
Osatehtävä 1 (11 pistettä)
- 1 \le n, q \le 1000
- 1 \le x, p_i \le 1000
Osatehtävä 2 (43 pistettä)
- 1 \le n, q \le 10^5
- 1 \le x, p_i \le 10^5
- kaikki kyselyt ovat tyyppiä 2
Osatehtävä 3 (46 pistettä)
- 1 \le n, q \le 10^5
- 1 \le x, p_i \le 10^5