루미 알고리즘

#1637플래티넘Counting Islands

PO 2026 결선코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Did you know that Sweden is the country with the most islands in the world? There are about 267,000 in total. However, many of these islands are very small.

Perhaps it is more relevant to ask which country has the most islands if we only count islands with a land area larger than 100m^2, or maybe 1000m^2?

There are N countries, numbered from 1 to N. Using the internet, you have found the sizes of all islands in these countries.

To satisfy your curiosity, you want to quickly determine which country has the most islands when counting only those with at least A square meters of land area. You have Q different values of A that you are curious about.

Input

The first line of the input contains the integers N and Q (1 ≤ N, Q ≤ 10^5), the number of countries and the number of queries.

The next N lines each describe the islands of one country. Each of these lines starts with an integer c (1 ≤ c ≤ 3 · 10^5), the number of islands in that country. This is followed by c integers s_1, …, s_c (1 ≤ s_i ≤ 10^9), the sizes of the country's islands.

Finally, Q lines follow, each containing an integer A (1 ≤ A ≤ 10^9), describing the value of A for a query.

Let T be the total number of islands, that is, T = ∑ c. It is guaranteed that T ≤ 3 · 10^5.

Output

For each query, print one integer: the index of the country that has the most islands if you only count the ones with a land area of at least A square meters. If two countries are tied for first place (have the same number of islands), then you should answer the one with the higher index.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
110N, T, Q ≤ 1000
213s_i, A ≤ 10
316N ≤ 2
422N ≤ 25
539No additional constraints.

Explanation of Sample 1

In the first query of sample case 1, country 1 has three islands with an area of at least 1m^2: 3, 7, 9. Country 2 has four islands with an area of at least 1m^2: 1, 2, 2, 3. Therefore, country 2 has the most islands.

In the second query, country 1 has two islands that are counted, while country 2 has no islands at all.

Explanation of Sample 2

In the first query of sample case 2, there are no islands at all with an area of at least 4m^2. Therefore, all countries have the same number of islands, and the answer is 2, the country with the highest index.

예제

예제 1

입력
2 2
3 3 7 9
4 1 2 2 3
1
4
출력
2
1

예제 2

입력
2 3
1 3
1 2
4
2
1
출력
2
2
2

출처 표기

출처: Programmeringsolympiaden 2026년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.