29448번 - Принцесса 스페셜 저지다국어

문제

Принцесса Евлампия живет в замке, окруженном забором. Жизнь принцессы тяжела, но при этом и очень интересна. Главным ее развлечением является общение с многочисленными поклонниками, постоянно прибывающими из соседних замков, городов и даже королевств.

Замок принцессы окружен забором, представляющим из себя выпуклый многоугольник. Отец принцессы, король, достаточно строг, поэтому всем поклонникам принцессы приходится попадать туда через единственную во всем заборе дырку, вместо того, чтобы войти на территорию замка через какие-нибудь парадные ворота. Дырка находится в одной из вершин многоугольника. При этом, если пройти напрямую к дырке поклоннику не удается, ему приходится обходить забор вдоль его периметра. Естественно, каждому поклоннику интересно, сколько ему придется пройти, чтобы попасть из точки своего начального местоположения к дырке, и все спрашивают об этом принцессу, перед тем как прийти к ней в гости.

Принцесса составила список начальных местоположений всех своих поклонников и описание забора вокруг замка. Вам необходимо для каждого поклонника сообщить длину кратчайшего пути от точки его начального положения до точки, в которой находится дырка. При этом, естественно, ни одна точка этого пути не должна лежать внутри многоугольника, представляющего забор, но может лежать на его границе.

입력

В первой строке входного файла находятся два целых числа $n$ и $k$(3ドル \le n \le 100,000,ドル 1ドル \le k \le n$) --- количество вершин в многоугольнике, представляющем забор, и номер вершины, в которой находится дырка. В следующих $n$ строках содержатся пары целых чисел $x_i$ и $y_i,ドル описывающих координаты вершин многоугольника в порядке обхода против часовой стрелки.

В следующей строке дано одно целое число $m$(1ドル \le m \le 100,000$) --- количество поклонников принцессы. В следующих $m$ строках содержатся пары целых чисел $x_i$ и $y_i,ドル описывающих координаты начального положения очередного поклонника.

Все координаты не превышают 10ドル^9$ по абсолютной величине.

출력

Для каждого поклонника выведите одно число --- ответ на задачу. Ответ должен отличаться от правильного не более, чем на 10ドル^{-5}$.

제한

힌트