CSES - Harjoituskisa 14.1.2018 - Pizzeriat
  • 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ä:

  1. rakennuksen k pizzan hinnaksi tulee x
  2. 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