영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
(그림은 원문 저장소에서 볼 수 있습니다)
Sand (https://commons.wikimedia.org/wiki/File:Morocco_Africa_Flickr_Rosino_December_2005_84527213.jpg), CC BY-SA 2.0
Sandra has moved to Sandsvall to study. After spending a few days in the new city, Sandra has noticed that there is quicksand in several locations. If you go to any of these locations, you get stuck in the sand and cannot escape. Sandra wants to know exactly where the quicksand is located so she can avoid these places. Fortunately, unlike Gothenburg, Sandsvall has a well-functioning travel planning app. Using the travel planner, Sandra has found out how long it takes to travel from her residence to each of the other locations in the city.
Sandsvall can be represented by a grid with N rows and M columns. Sandra's residence is in one of the cells of this grid. It takes one minute to travel between two adjacent cells (two cells are adjacent if they share at least one of the 4 sides). In some cells, there is quicksand, and it is impossible to travel from those cells at all.
Let (r, c) be the cell at row r and column c. You are given the number d_{r,c} for each cell in the grid, which represents the minimum possible number of minutes it takes to travel from Sandra's residence to that cell. Your task is to handle Q queries of the following types:
? r c: Determine if there is quicksand in cell (r, c). You should answerja(yes),nej(no),kanske(maybe), orfel(error).! r c d: Change the value of d_{r, c} to d.
Input
The first line contains three integers N, M, and Q (1 ≤ N,M,Q ≤ 3 · 10^5, N · M ≤ 3 · 10^5).
The following N lines contain M integers each. The i-th of these lines contains the integers d_{i,1}, d_{i,2}, d_{i,3}, … d_{i,M} (-1 ≤ d_{i,j} ≤ 3 · 10^5).
There will be exactly one cell that satisfies d_{r, c} = 0, which is Sandra's residence. If d_{r, c} = -1, it means that it is impossible to reach cell (r, c) at all.
The following Q lines contain the queries to be processed, in the format described above. The numbers r, c that appear in the queries satisfy 1 ≤ r ≤ N and 1 ≤ c ≤ M. The numbers d that appear satisfy -1 ≤ d ≤ 3 · 10^5, d ≠ 0. Sandra's residence will always have a distance of zero, and no other cell's distance will be changed to zero.
Output
Write the answer to each query of the form ? r c.
- If there is no way to distribute the quicksand that is consistent with the given numbers d, you should output
fel. - Otherwise, if there must be quicksand in cell (r, c), output
ja. - If there is guaranteed to be no quicksand in cell (r, c), output
nej. - If it is both possible and not possible for there to be quicksand in cell (r, c), output
kanske.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 17 | N = 1 |
| 2 | 28 | N,M,Q ≤ 100 |
| 3 | 20 | The answer is never fel. |
| 4 | 35 | No additional constraints. |
Explanation of Sample
(그림은 원문 저장소에서 볼 수 있습니다)
This is what the grid looks like in the sample case.
In the first query, we need to determine if (3, 5) (highlighted in gray) has quicksand, and it must have it. In the third query, we need to determine if (1, 6) has quicksand, and it is impossible to determine because it is unreachable. After the update that changes the value of (5, 4) to 7, the distances no longer correspond to any valid distribution of quicksand.
예제
예제 1
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