26642번 - Ryki 다국어

Berlandia to nieskończona plansza złożona z kwadratowych pól. Wiersze są ponumerowane rosnącymi liczbami całkowitymi od dołu do góry, a kolumny od lewej do prawej. Niech $(r, c)$ oznacza pole na przecięciu wiersza $r$ i kolumny $c$. Dwa różne pola nazywamy sąsiadującymi jeśli dotykają się przynajmniej rogiem. Oznacza to, że każde pole ma dokładnie ośmiu sąsiadów.

Odległość między dwoma polami $(R_A, C_A)$ i $(R_B, C_B)$ to odległość Euklidesowa, to jest:

$$\sqrt{(R_A - R_B)^2 + (C_A - C_B)^2}\text{.}$$

W Berlandii żyje $n$ niedźwiedzi. Niedźwiedź o numerze $i$ zamieszkuje pole $(r_i, c_i)$. W jednym polu może znajdować się wiele niedźwiedzi.

Niedźwiedzie potrafią żyć samotnie, ale każdy czasem potrzebuje bliskości. Gdy jeden z niedźwiedzi zaryczy, wszystkie niedźwiedzie z innych pól natychmiastowo zbliżą się o jedno pole do ryczącego, przechodząc do tego z sąsiadujących pól, które jest najbliżej pola z ryczącym niedźwiedziem. Można udowodnić, że zawsze jest dokładnie jedno takie pole (nie ma remisów). Niedźwiedzie, które znajdują się w tym samym polu co ryczący, nie zmieniają swojego położenia.

Przykładowo, rozważmy parę niedźwiedzi, jednego w polu $(2, 1)$, a drugiego w polu $(4, 8)$. Ryk w polu $(2, 1)$ sprawi, że drugi niedźwiedź przechodzi do pola $(3, 7)$, które jest w odległości $\sqrt{(3 - 2)^2 + (7 - 1)^2} = \sqrt{37}$ od źródła ryku.

Niedźwiedzie zaryczą w kolejności $1, 2, \dots , n$, każdy raz. Każdy poza jednym.

Limak jest przeziębiony. Nie jest w stanie zaryczeć i nie może on opuścić swojej gawry, więc pozostanie w swoim początkowym polu. Biedny Limak.

Nie wiesz, którym niedźwiedziem jest Limak. Dla każdego $k$ od $1$ do $n$, znajdź końcowe położenie niedźwiedzi, jeśli $k$-ty z nich to Limak. Dla każdej możliwości wypisz sumę iloczynów końcowych współrzędnych, to jest przyjmując, że $i$-ty niedźwiedź po wszystkich $n - 1$ rykach jest w polu $(r′_i , c′_i )$:

$$\displaystyle \sum_{i=1}^{n}{r'_i \cdots c'_i}$$

Pierwszy wiersz wejścia zawiera liczbę całkowitą $n$ ($2 ≤ n ≤ 250\,000$) – liczbę niedźwiedzi.

Kolejne $n$ wierszy zawiera dwie liczby całkowite $r_i$, $c_i$ ($1 ≤ r_i , c_i ≤ 10^6$) – $i$-ty z nich oznacza początkowe położenie $i$-tego niedźwiedzia.

Wypisz $n$ wierszy. W $k$-tym z nich powinna znaleźć się pojedyncza liczba całkowita – suma iloczynów końcowych współrzędnych przy założeniu, że Limak jest k-tym niedźwiedziem.