时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
MCM/ICM is just as interesting as ACM/ICPC.
If you have participated in MCM/ICM 2019, then you will definitely know about the Problem D about the Louvre.
Qleonardo also participated in this MCM/ICM. To solve this problem, qleonardo thought of using the cellular automaton model to simulate the evacuation process. However, we are now doing ACM instead of MCM/ICM, so we simplified his model.
Specifically, the plane map of the Louvre is first divided into a number of small squares. Then abstract the person into points and put them in these small squares.
This way we can let everyone move in a specific way. Specifically, we can move everyone to the nearest exit to reduce the time spent on evacuation. However, the size of the exit is fixed. We assume that an exit can only go out of one person per unit time, and each person moves at a speed of 1. In addition, we believe that it is more spacious except for the exit. That is to say, there can be multiple people in a small square in the places except for the exit.
When multiple people want to go out from an exit at the same time, these people will rush out to survive. Therefore, the strongest person will first go out from this exit, and the others will stop in their original position.
Your task is to output the time each person flees the Louvre in accordance with the above rules.
You should be aware that people cannot cross obstacles and can only escape from the exit. If a person is at the same distance from the two exits, then the upper exit is preferred. If there is still the same, the left exit is preferred.
输入描述:
The first line consists of three numbers m,n(2<=n,m<=1,000) and p(1<=p<=1,000,000), representing the width andlength of the Louvre plane map and the number of initial people.
Next, a matrix of m*n, 0 means that acertain position can go, 1 means an obstacle, and 2 means an exit.
Next there are p lines, three numbers xi,yi (1<=xi<=m,1<=yi<=n) and wi (0<=wi<=2^31-1) for each line,indicating the initial position coordinates of the i-th person and hisstrength.
Dataguarantees that everyone’s strength is different. Data guarantees thateveryone's initial position is not an obstacle nor an exit.
输出描述:
Output a line, a total of p numbers, wherethe i-th number indicates the time when the i-th person escaped from theLouvre.
Ifsomeone can't get to the exit, the person's escape time is -1.