TopCoder

User's AC Ratio

87.8% (72/82)

Submission's AC Ratio

19.0% (111/585)

Description

阿華很喜歡玩益智遊戲,昨天他拿到一個遊戲,規則是這樣的:在一個 N×M 的棋盤上有一個水晶球,給定它的起始位置和目標位置,阿華必須將水晶球從起始位置移動到目標位置。移動的次數和移動的距離也是給定的,阿華只能決定移動的方向:上、下、左或右。舉個例子:下圖是一個 4×6 的棋盤,水晶球的起始位置是 (1, 1),目標位置是 (3, 5)。

如果指定水晶球必須移動三次,每次移動的距離依序是 1, 2, 3,則阿華可以將水晶球向「上」移動1 格、向「左」移動2 格,再向「下」移動3 格,即可抵達目標位置。(或是「右」、「下」、「右」也可以。)移動過程中,如果超出棋盤邊界,則會從另一頭繼續移動,例如上面的第一種解法,水晶球從 (0, 1) 向左移動2 格,會移動至 (0, 5) 這個位置。
一開始的關卡很簡單,阿華一下子就完成了。但是有一個關卡阿華想了很久,他認為這個關卡是不可能達成的。現在請你寫一個程式,幫阿華確認一個關卡是不是有可能達成。(阿華自尊心很強,你不需要告訴他該如何移動水晶球,只要告訴他這個關卡是否可能達成。)

Input Format

輸入的第一行有兩個數字 N 和 M (1 ≤ N, M ≤ 100),代表棋盤大小。第二行有四個數字 X1, Y1, X2, Y2,代表水晶球的開始位置 (X1, Y1) 和目標位置 (X2, Y2)。第三行的第一個數字 K (1 ≤ K ≤ 10,000) 為正整數,代表可移動幾次,接下去有 K 個正整數 d1, d2, …, dK(≤ 100),代表移動的距離。兩個整數之間都以一個空格隔開。

Output Format

請輸出是否可能將水晶球移至目標位置。若可以,印出 YES,否則印出 NO。

Sample Input

輸入檔範例1
4 6
1 1 3 5
3 1 2 3

輸入檔範例2
2 2
0 0 1 1
2 2 2

輸入檔範例3
2 2
0 0 1 1
2 1 1

Sample Output

輸出檔範例1
YES

輸出檔範例2
NO

輸出檔範例3
YES

Hints

Problem Source

臺北市103學年度高級中學資訊學科能力競賽程式設計試題第一題
Set by Paupière
若測資有誤請儘快聯絡管管(?

Subtasks

No. Testdata Range Constraints Score
1 0~4 1 ≤ N, M ≤ 5,K = 2 10
2 5~9 1 ≤ N, M ≤ 50,1 ≤ K ≤ 5 30
3 10~14 1 ≤ N, M ≤ 100,1 ≤ K ≤ 20 30
4 15~19 1 ≤ N, M ≤ 100,1 ≤ K ≤ 10,000 30

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 524288 262144 1
1 5000 524288 262144 1
2 5000 524288 262144 1
3 5000 524288 262144 1
4 5000 524288 262144 1
5 5000 524288 262144 2
6 5000 524288 262144 2
7 5000 524288 262144 2
8 5000 524288 262144 2
9 5000 524288 262144 2
10 5000 524288 262144 3
11 5000 524288 262144 3
12 5000 524288 262144 3
13 5000 524288 262144 3
14 5000 524288 262144 3
15 5000 524288 262144 4
16 5000 524288 262144 4
17 5000 524288 262144 4
18 5000 524288 262144 4
19 5000 524288 262144 4