eolymp
bolt
Try our new interface for solving problems
Problems

Queen (RU)

Queen (RU)

Time limit 1 second
Memory limit 64 MiB

На обобщенной шахматной доске (размерами не обязательно 8×8)стоит ферзь. Известно, на какой клетке он находится сейчас и в какую клетку ему необходимо добраться. Задача усложняется тем, что некоторые клетки заняты фигурами соперника, но упрощается тем, что сейчас они крепко спят, так что ферзь может тихонько сделать сколько угодно ходов подряд. Ни перепрыгивать через фигуры соперника, ни бить их нельзя (ибо тогда они проснутся).

Напишите программу, определяющую минимальное количество ходов, необходимых ферзю для такого перемещения.

Input data

Программа читает с клавиатуры размеры шахматной доски — сначала количество вертикалей w (2w26), затем количество горизонталей h (2h99), затем координаты стартовой и финишной клеток, затем количество фигур соперника К (0Kw·h2), далее K пар чисел – координаты очередной фигуры соперника. Все числа разделяются пробелом. Координаты всех клеток – натуральные числа, не превосходящие w та h Сначала вводится вертикаль, потом горизонталь. Клетки, указанные как начальная и конечная, не содержат фигур соперника; разные фигуры не могут находиться в одной и той же клетке.

Output data

Программа должна вывести на экран единственное целое число — либо минимальное количество ходов, необходимых, чтобы дойти от указанной начальной клетки до указанной конечной, либо -1, если дойти невозможно соответственно.

Examples

Input example #1
8 8 5 2 5 4 1 5 3
Output example #1
2