4659 . Constructive
Description
本題是Batch題
有一間「環面向量量販店」舉辦「蓋向量體驗活動」。當然，畢竟它是「環面向量量販店」，所以它所供應的向量都是在環面上的向量。更精確來說，這間店所供應的向量，都是在長度是$X$，寬度是$Y$的環面上。這個環面上各點都能用實數數對$(x, y)$表示，但因為這畢竟是環面，所以$(x, y), (x + X, y), (x, y + Y)$表示的點是一樣的。同樣的，我們也能用實數數對來表示這個環面上的向量，且$(x, y), (x + X, y), (x, y + Y)$表示的向量也是一樣的。向量的相加也和我們平常所認識的平面向量相加一樣，就是把對應的分量相加。
一開始這間店沒有任何向量可以供應。活動期間發生了$Q$件事情，每件事情都是以下二種之一：
0. 這間店進口了向量$v = (v_x, v_y)$，此後它就能無限供應這種向量。顧客每取用一個這種向量，就要花費$c$元。
1. 有一位顧客想要蓋出向量$u = (u_x, u_y)$。他可以從當下這間店供應的向量之中任意取用若干個向量，然後把它們相加來得到$u$向量，當然就要支付相應的費用。在蓋向量之前，這位顧客想要了解蓋出$u$向量最少要花多少錢，或是利用當下供應的向量根本蓋不出$u$向量。
Input Format
每筆測資第零行是三個正整數$X, Y, Q$，以空格分開
接下來$Q$行，每行有四或三個整數，以空格分開，若第$1 + i$行有四個正整數，代表第$i$件事情是第0種，四個整數依序是$0, v_x, v_y, c$，若第$1 + i$行有三個正整數，代表第$i$件事情是第1種，三個整數依序是$1, u_x, u_y$
$1 \le X, Y \le 1000, 1 \le Q \le 5 \times 10^ {5}$
第0種事情最多發生$15$次
對於第0種事情，有$-10^ {9} \le v_x, v_y \le 10^ {9}, 1 \le c \le 10^ {9}$
對於第1種事情，有$-10^ {9} \le u_x, u_y \le 10^ {9}$
Output Format
對於每一件的第1種事情，輸出一行答案，若能蓋出$u$向量則於該行輸出最少要花幾元，否則輸出-1
Sample Input 1
4 4 4 1 0 0 0 100 200 777771449 1 777771449 777771449 1 8 8
Sample Output 1
0 -1 0
Sample Input 2
5 7 7 0 -777771449 -777771449 777771449 1 67 67 1 67 0 0 8 8 8 1 8 8 1 9 1000000 1 -1000000 -999999
Sample Output 2
-1 1555542898 8 64 0
Sample Input 3
3 3 11 0 1 1 7 0 2 1 8 1 0 0 1 0 1 1 0 2 1 1 0 1 1 1 1 1 2 1 2 0 1 2 1 1 2 2
Sample Output 3
0 30 15 22 7 16 23 8 14
Sample Input 4
1000 1000 2 0 1001 1001 777771449 1 333 333
Sample Output 4
258997892517
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~3 | 範例測資 | 0 |
| 2 | 4~13 | 只會發生第0種事情 | 1 |
| 3 | 14~23 | 只會發生第1種事情 | 1 |
| 4 | 0, 3, 14~43 | 第0種事情至多發生一次 | 9 |
| 5 | 2~23, 44~63 | 第1種事情必然在所有的第0種事情之後發生 | 22 |
| 6 | 0~83 | 無特別限制 | 67 |