Problem B
Kvicksand

Sand, CC BY-SA 2.0

Sandra har flyttat till Sandsvall för att studera. Efter att ha tillbringat några dagar i den nya staden har Sandra märkt att det finns kvicksand på flera platser. Om man åker till någon av dessa platser så fastnar man i sanden och kan inte ta sig därifrån. Sandra vill ha reda på exakt var kvicksanden finns för att kunna undvika dessa platser. Som tur är har Sandsvall, till skillnad från Göteborg, en välfungerande reseplaneringsapp. Med hjälp av reseplaneraren har Sandra tagit reda på hur lång tid det tar att åka från hennes bostad till var och en av de andra platserna i staden.

Sandsvall kan representeras av ett rutnät med $N$ rader och $M$ kolumner. Sandras bostad är i en rutorna i detta rutnät. Det tar en minut att åka mellan två närliggande rutor (två rutor är närliggande om de delar minst en av 4 de sidorna). I vissa rutor finns det kvicksand, och då går det inte att åka därifrån alls.

Låt $(r, c)$ vara rutan på rad $r$ och kolumn $c$. Du får givet talet $d_{r,c}$ för varje ruta i rutnätet, det minsta möjliga antalet minuter det tar att åka från Sandras bostad till rutan. Din uppgift är att hantera $Q$ frågor av följande slag:

• ? r c: Avgör om det finns kvicksand på ruta $(r, c)$. Du ska svara ja, nej, kanske, eller fel.

• ! r c d: Ändra värdet på $d_{r, c}$ till $d$.

Indata

Den första raden innehåller tre heltal $N$, $M$ och $Q$ ($1 \leq N,M,Q \leq 3 \cdot 10^5$, $N\cdot M \leq 3 \cdot 10^5$).

Följande $N$ rader innehåller $M$ heltal var. Den $i$te av dessa rader innehåller heltalen $d_{i,1}, d_{i,2}, d_{i,3}, \dots d_{i,M}$ ($-1 \leq d_{i,j} \leq 3 \cdot 10^5$).

Det kommer finnas exakt en ruta som uppfyller $d_{r, c} = 0$, detta är Sandras bostad. Om $d_{r, c} = -1$ så innebär det att det inte går att ta sig till ruta $(r, c)$ alls.

Följande $Q$ rader innehåller frågorna som ska behandlas, på formatet ovan. Talen $r, c$ som förekommer i frågorna uppfyller $1 \leq r \leq N$ och $1 \leq c \leq M$. Talen $d$ som förekommer uppfyller $-1 \leq d \leq 3 \cdot 10^5$, $d \neq 0$. Sandras bostad kommer alltid ha avståndet noll, och inga andra rutors avstånd kommer ändras till noll.

Utdata

Skriv ut svaret på varje fråga på formen ? r c.

• Om det inte finns något sätt som kvicksanden kan vara fördelad på som är konsekvent med de givna talen $d$ ska du skriva ut fel.

• Annars, om det måste finnas kvicksand på ruta $(r, c)$, skriv ut ja.

• Om det garanterat inte finns kvicksand på ruta $(r, c)$, skriv ut nej.

• Om det både kan och inte kan finnas kvicksand på ruta $(r, c)$, skriv ut kanske.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall

Så här ser rutnätet i exempelfallet ut. I den första frågan så ska vi avgöra om $(3, 5)$ (gråmarkerad) har kvicksand, och det måste den ha. I den tredje frågan ska vi avgöra om $(1, 6)$ har kvicksand, och det är omöjligt att avgöra eftersom den är omöjlig att nå. Efter uppdateringen som ändrar värdet hos $(5, 4)$ till $7$ så stämmer inte avstånden överens med någon utplacering av kvicksand.

5 6 7
2 3 4 5 6 -1
1 2 3 4 5 6
0 1 4 5 6 -1
1 2 3 6 7 -1
2 3 4 5 6 -1
? 3 5
? 2 4
? 1 6
! 5 4 7
? 5 3
! 5 6 7
? 1 6

ja
nej
kanske
fel
fel