Era Name
Time limit8sMemory limit512 MB
Given partial records mapping Western years to era names and regnal years, determine the era name and year for each query, or report Unknown when no record covers it.
- Level
Medium4 of 10
- Topics
- Array, Sorting, Intervals, Implementation
- Solved
- No attempts yet
Problem
Japan uses two calendar systems today. One is the Gregorian calendar used across much of the world, called the Western calendar in Japan.
The other is the era-based calendar, also called the Japanese calendar. This system comes from ancient Chinese systems, and in recent Japanese practice it ties dates to the Emperors. In the era-based system a year is written with the era name chosen when a new Emperor assumes the throne. If the era name is A, the first regnal year is "A 1", the second year is "A 2", and so on.
Because there are two calendar systems, dates often have to be converted from one to the other. In this problem you write a program that converts a Western year to its era-based year, given a database that records the association between several Western years and era-based years.
For simplicity, assume the following.
- A new era always begins on January 1st of the corresponding Gregorian year.
- The first year of an era is written as 1.
- There is no year in which more than one era switch takes place.
The database you are given may be incomplete. Some era that existed in history may be missing from your data, so you also have to detect the cases where you cannot determine exactly which era the given year belongs to.
A database entry says that Western year is year of era , so era runs at least from Western year through year . If the queried year lies in none of those determined ranges, an era absent from the data may have covered that year, so the era cannot be determined.
Input
The input contains several datasets. Each dataset has the following format.
N Q
EraName1 EraBasedYear1 WesternYear1
.
.
.
EraNameN EraBasedYearN WesternYearN
Query1
.
.
.
QueryQ
The first line of a dataset contains two positive integers and (, ). is the number of database entries and is the number of queries.
Each of the following lines has three components: an era name, an era-based year number, and the corresponding Western year (). Each era name consists of at most 16 Roman alphabet characters. The last lines of the dataset each specify a query (), a Western year to convert to its era-based representation.
The end of the input is indicated by a line containing two zeros. That line is not part of any dataset and must not be processed.
Every Western year in the input is a positive integer, and no two entries share the same era name.
Output
For each query, output the era name and the era-based year number corresponding to the given Western year on one line, separated with a single space. If you cannot determine the era, output Unknown without the quotes.