Contest problemset description

Państwo Bajtocji składa się z N miast połączonych między sobą dokładnie N dwukierunkowymi drogami. Ponadto z każdego miasta można dojechać do dowolnego innego.

Burmistrz Bajtocji zainteresował się infrastrukturą drogową swojego kraju. Zaczął się zastanawiać jaki jest stopień rozległości sieci drogowej. Stopień rozległości zdefiniował jako sumę długości najkrótszych ścieżek między każdą parą miast. Jako jego najlepszy doradca, pomóż mu i napisz program, który policzy stopień rozległości Bajtocji.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N oznaczająca liczbę miast Bajtocji. W następnych N wierszach znajduje się opis dróg Bajtocji. Każdy z nich składa się z trzech liczb u, v, w oznaczających, że miasta o numerach u oraz v połączone są drogą o długości w. Możesz założyć, że każda para miast występuje na wejściu co najwyżej raz.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą oznaczającą stopień rozległości Bajtocji.

Ograniczenia

1 ≤ N ≤ 1 000 000, 1 ≤ u, v ≤ N, 1 ≤ w ≤ 1 000 000.

W testach wartych 20% punktacji zachodzi warunek N ≤ 2 000.

Przykład

5
1 2 1
2 3 2
3 4 3
4 2 4
5 4 5

50

Jasio zarządza lokalnym sklepem. W sklepie jest N regałów ustawionych jeden obok drugiego. Na każdym regale leżą przedmioty jednego rodzaju, który oferuje sklep Jasia. Rodzaje przedmiotów ponumerowane są liczbami naturalnymi od 1 do N. Jasio co jakiś czas decyduje, żeby zmienić typ przedmiotów na niektórych regałach. Musi również co jakiś czas przeprowadzać inwentaryzację. Pojedyncza inwentaryzacja polega na sprawdzeniu liczby regałów w przedziale od l-tego do r-tego, które mają wystawione przedmioty o ustalonym rodzaju v. Jasio poprosił Cię o napisanie systemu, który pozwoli mu przyspieszyć proces inwentaryzacji.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz Q, oznaczające odpowiednio liczbę regałów oraz liczbę zapytań Jasia. W drugim wierszu wejścia znajduje się N liczb naturalnych p₁, …, p_N oznaczające początkowe rodzaje przedmiotów na kolejnych regałach sklepu Jasia. W następnych Q wierszach następuje opis zapytań. i-ty opis rozpoczyna się od jednego znaku t_i. Jeżeli t_i = Z, to w tym samym wierszu następują dwie liczby naturalne z_i, v_i oznaczające, że Jasio zmienił rodzaj przedmiotów na z_i-tym regale na v_i. Jeżeli t_i = I, to w tym samym wierszu następują trzy liczby naturalne v_i, l_i, r_i oznaczające, że Jasio chce przeprowadzić inwentaryzację regałów od l_i-tego do r_i-tego włącznie dla przedmiotów o rodzaju v_i.

Wyjście

Dla każdego zapytania typu I należy wypisać jedną liczbę naturalną odpowiadającą na dane pytanie Jasia.

Ograniczenia

1 ≤ N, Q ≤ 500 000, 1 ≤ v_i, p_i, z_i ≤ N, 1 ≤ l_i ≤ r_i ≤ N.

W testach wartych łącznie 20% punktów zachodzi dodatkowy warunek N, Q ≤ 2000.

W testach wartych łącznie 40% punktów zachodzi dodatkowy warunek t_i = I dla każdego i.

Przykład

3 4
1 2 3 
I 1 1 3
Z 2 1
I 1 1 2
I 2 2 3

1
2
0

Firma telekomunikacyjna JANUSZKOM postanowiła rozstawić N przekaźników radiowych wzdłuż kraju. Przekaźniki ustawione będą na jednej prostej. Dla każdego z przekaźników wyznaczone zostały dwie możliwe współrzędne, na którym powinien znaleźć się dany przekaźnik. Dla każdego z przekaźników należy wybrać jedną z tych współrzędnych. Ponadto chcielibyśmy, żeby przekaźniki zostały rozstawione możliwie równomiernie. Formalnie, chcielibyśmy, żeby minimalna odległość między pewną parą przekaźników była największa możliwa.

Oczywiście to zadanie zostało powierzone Tobie. Napisz program, który wyznaczy wartość największej możliwej minimalnej odległości między pewną parą przekaźników.

Wejście

W pierwszym wierszu wejścia dana jest jedna liczba naturalna N oznaczająca liczbę przekaźników. W następnych N wierszach dany jest opis możliwych współrzędnych każdego z przekaźników. i-ty opis składa się z dwóch liczb x_i, y_i oddzielonych pojedynczą spacją i oznaczające możliwe położenie i-tego przekaźnika.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita oznaczającą maksymalną minimalną odległość między pewną parą przekaźników.

Ograniczenia

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

W testach wartych 10% punktacji zachodzi dodatkowy warunek N ≤ 20.

W testach wartych 50% punktacji zachodzi dodatkowy warunek N ≤ 2 000.

Przykład

3
1 3
2 5
1 9

4