實驗室警鈴大作，你聽廣播後得知在$t$秒前，位於$V$有人不小心將試管打破，導致病毒外漏。該病毒傳播迅速，如果在某個時間內某個區域已經有病毒，則下一秒病毒就會擴散到相鄰的區域。因為該種病毒很怕陽光，所以有陽光的區域不會有病毒。整個實驗室唯一有陽光的地方是$S$，你現在在$P$，你決定逃到$S$，等待救援。你每秒只能從當前的區域移動到相鄰的區域，並且你不想到有病毒的區域，因為沒有人知道這個病毒的副作用是什麼。
第一行有三個整數$n, m, t,\ (1\leq n, m\leq1000,\ 0\leq t\leq1000000)$，代表實驗室的大小為$n\times m$，並且$t$秒前試管被打破。
接下來有$n$行，每行是一個長度為$m$的字串。這$n$行是實驗室的地圖，左上角為$(0, 0)$，右下角是$(n-1, m-1)$，標記為*的是牆壁，人和病毒都不能通行；標記為$P$的是你現在的位置；標記為$V$的是病毒外漏的區域；標記為$S$的是有陽光的區域；剩下的區域則標記為.。
若可以到達$S$，請輸出最少需要幾秒；若無法到達$S$，請輸出"Goodbye world!"。
TOIJ 1013
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~12 | 無額外限制 | 100 |