Однажды Петя получил на день рождения набор деревянных кубиков в подарок от своей мамы. Недолго думая, Петя построил из этих кубиков целый город.
Город в основании представляет собой квадрат размера n × n, разделенный на единичные квадратики. Стороны квадрата параллельны осям координат, противоположные углы квадрата имеют координаты (0, 0) и (n, n). На каждом из единичных квадратиков Петя построил башню из деревянных кубиков. Сторона деревянного кубика также имеет единичную длину.
После этого Петя отошел от своего творения на бесконечно большое расстояние и посмотрел на него в направлении вектора v = (vx, vy, 0). Петю интересует сколько различных кубиков видно из этого положения. Помогите ему, найдите это количество.
Каждый кубик включает в себя свою границу. Считается, что кубик видно, если существует луч, выходящий из некоторой точки p, принадлежащей кубику, в направлении вектора - v, который не содержит точек, принадлежащих другим кубикам.
Выходные данные
Выведите единственное целое число — количество видимых кубиков.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.