Contest problemset description

Każdy wie, że należy dbać o swoje dobre imię. Wie o tym również Jasio, który jakość imienia wycenia w następujący sposób: każda litera a daje jeden punkt, każda litera b dwa punkty, c trzy punkty i tak dalej aż do z, które daje aż dwadzieścia sześć punktów. Punkty za wszystkie litery należy zsumować. Im większa suma wartości liter, tym lepsze imię. A przynajmniej tak jest dla Jasia. W tym zadaniu używamy jedynie alfabetu angielskiego.

Jasio chce popracować nad swoim imieniem i wymienić w nim co najwyżej jedną literę na inną, w taki sposób, żeby zmaksymalizować wartość jego imienia. Ponieważ imiona warte dużo punktów są cool, zapewne koledzy Jasia również będą chcieli wymienić swoje imiona na nowe, lepsze. Pomóż mu więc i napisz program, który wczyta imię, wyznaczy jakie najlepsze imię można uzyskać zamieniając co najwyżej jedną literę na inną i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się niepusty ciąg małych liter alfabetu angielskiego – imię.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinien się znaleźć niepusty ciąg małych liter alfabetu angielskiego – najlepsze możliwe imię po poprawkach.

Jeżeli istnieje wiele możliwych poprawnych odpowiedzi, Twój program może wypisać dowolną z nich.

Ograniczenia

Długość imienia nie przekracza 1 000 000 znaków.

Przykład

jasio

jzsio

jadziula

jzdziula

z

z

Liczbę naturalną nazywamy dobrą, jeżeli spełnia ona następujące trzy warunki jednocześnie:

• ma N cyfr w systemie dziesiętnym,
• nie ma zer wiodących,
• zawiera co najmniej jedną cyfrę 1.

Napisz program, który: wczyta liczbę naturalną N, wyznaczy ile jest liczb dobrych i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba naturalna N.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć liczba liczb dobrych.

Ograniczenia

1 ≤ N ≤ 18.

Przykład

2

18

Na niektórych polach prostokątnej planszy znajdują się roboty. Każdy robot ma umieszczone cztery kamery pozwalające mu zobaczyć każdego innego robota (o ile takie są) w jednym z czterech podstawowych kierunków (góra, dół, lewo, prawo), w tym samym wierszu lub tej samej kolumnie, w której ów robot się znajduje.

Napisz program, który: wczyta pozycje robotów, wyznaczy liczbę par robotów, które widzą się nawzajem i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca liczbę robotów. W kolejnych N wierszach znajdują się pary liczb x_i oraz y_i, oddzielone pojedynczym odstępem. Są to współrzędne pola, na którym znajduje się i-ty robot, odpowiednio numer wiersza oraz numer kolumny.

Wiersze i kolumny numerowane są kolejnymi liczbami naturalnymi.

Gwarantowane jest, że pozycje wszysktich robotów są parami różne.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – liczba (nieuporządkowanych) par robotów, które się widzą nawzajem.

Ograniczenia

1 ≤ N ≤ 500 000, 1 ≤ x_i, y_i ≤ 10⁹.

Przykład

6
5 5
2 2
2 4
4 2
2 5
3 6

5