Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MWP4_1D - Load-Balancer

W sieci pewnej korporacji doszło do skrajnego naruszenia zasad bezpieczeństwa! Ktoś próbował włamać się na serwer! To skandal - pomyślał Administrator sieci - muszę namierzyć szkodnika. Pozostaje tylko jedno pytanie - Jak? Wytropienie intruza stało się obsesją Administratora, całymi dniami przeglądał logi i próbował odtworzyć moment włamania. Wszystko na nic, nasz dzielny Administrator nie potrafił poradzić sobie z Load-Balancerem. Znał kolejność w jakiej łączyli się klienci, wiedział dokładnie kiedy nawiązywali połączenie i kiedy się rozłączali. Domyślał się również, który z nich próbował przeprowadzić atak, ale nie miał pojęcia do którego serwera napastnik został przydzielony przez to wymyślne urządzenie...

Zlituj się nad Administratorem. Napisz program, który na podstawie logów określi do którego serwera trafił dany klient. Na wejściu otrzymasz dane z logu tj. listę klientów w kolejności zgodnej z kolejnością nawiązywania przez nich połączeń i liczbę serwerów na które ruch był balansowany. Na wyjściu należy wypisać dla danego klienta numer porządkowy serwera do którego został przydzielony. Load-Balancer przydziela użytkowników wyłącznie na podstawie liczby aktywnych sesji. Nowy klient trafia do najmniej obciążonego serwera. Jeżeli dwa lub więcej serwerów jest obciążonych w równym stopniu, wtedy połączenie trafia do tego o najniższym numerze porządkowym. Zakładamy, że serwer obsługuje zakończenie połączenia przed nawiązaniem kolejnego - tj. jeżeli sesja A trwa od sekundy 5 do 8 a sesja B od 8 do 10 należy założyć, że sesja B została nawiązana o pomijalny dla wyniku ułamek sekundy później niż zakończyła się sesja A.

Wejście

W pierwszej linii wejścia znajduje się liczba s (1 ≤ s ≤ 1000) określająca liczbę serwerów, na które rozkładany był ruch. W kolejnej linii znajduję się liczba klientów – k (1 ≤ k ≤ 200000), po której w następnych k-liniach zamieszczone są opisy klientów. Opis klienta to dwie liczby p i z (0 ≤ p < z ≤ 2 × 109) oznaczające odpowiednio moment nawiązania i zakończenia połączenia. Kolejną linię po opisie klientów stanowi liczba m (1 ≤ m ≤ 600000) określająca liczbę zapytań o klientów. W kolejnych m liniach znajdują się zapytania. Każde zapytanie składa się z pojedynczej liczby będącej numerem porządkowym klienta.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać numer porządkowy serwera, do którego został przypisany dany klient.

Przykład

Wejście:

3
8
0 5
0 2
2 5
6 10
7 9
7 15
9 20
9 11
3
3
6
8

Wyjście:

2
3
1

Dodane przez:Maciej Boniecki
Data dodania:2012-03-13
Limit czasu wykonania programu:0.100s-1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 SCM qobi
Pochodzenie:IV Mistrzostwa WWSI w Programowaniu

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.