Under construction

Still being built. Things may change

Era Name

Time limit8sMemory limit512 MB

Summary
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.

  1. A new era always begins on January 1st of the corresponding Gregorian year.
  2. The first year of an era is written as 1.
  3. 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 (A,k,y)(A, k, y) says that Western year yy is year kk of era AA, so era AA runs at least from Western year y−k+1y-k+1 through year yy. 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 NN and QQ (1≤N≤10001 \le N \le 1000, 1≤Q≤10001 \le Q \le 1000). NN is the number of database entries and QQ is the number of queries.

Each of the following NN lines has three components: an era name, an era-based year number, and the corresponding Western year (1≤EraBasedYeari≤WesternYeari≤1091 \le \text{EraBasedYear}_i \le \text{WesternYear}_i \le 10^9). Each era name consists of at most 16 Roman alphabet characters. The last QQ lines of the dataset each specify a query (1≤Queryi≤1091 \le \text{Query}_i \le 10^9), 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.

Examples7

  1. Example 1

    Input
    4 3
    meiji 10 1877
    taisho 6 1917
    showa 62 1987
    heisei 22 2010
    1868
    1917
    1988
    1 1
    universalcentury 123 2168
    2010
    0 0
    
    Expected output
    meiji 1
    taisho 6
    Unknown
    Unknown
    
  2. Example 2

    Input
    1 4
    reiwa 3 2021
    2019
    2021
    2018
    2022
    0 0
    
    Expected output
    reiwa 1
    reiwa 3
    Unknown
    Unknown
    
  3. Example 3

    Input
    2 5
    alpha 5 1005
    beta 1 1006
    1000
    1001
    1005
    1006
    1007
    0 0
    
    Expected output
    Unknown
    alpha 1
    alpha 5
    beta 1
    Unknown
    
  4. Example 4

    Input
    1 3
    z 1000000000 1000000000
    1
    500000000
    1000000000
    0 0
    
    Expected output
    z 1
    z 500000000
    z 1000000000
    
  5. Example 5

    Input
    1 2
    a 1 1
    1
    2
    2 3
    eranamesixteenxy 2 100
    Second 1 200
    99
    100
    200
    1 1
    Q 1 1000000000
    999999999
    0 0
    
    Expected output
    a 1
    Unknown
    eranamesixteenxy 1
    eranamesixteenxy 2
    Second 1
    Unknown
    
  6. Example 6

    Input
    5 8
    eee 10 5000
    aaa 3 100
    ddd 1 4000
    ccc 50 3000
    bbb 7 500
    98
    97
    494
    2951
    4000
    4001
    4991
    5001
    0 0
    
    Expected output
    aaa 1
    Unknown
    bbb 1
    ccc 1
    ddd 1
    Unknown
    eee 1
    Unknown
    
  7. Example 7

    Input
    3 6
    ABCDEFGHIJKLMNOP 16 1016
    abcdefghijklmnop 1 1017
    MixedCaseEraXYZ 2 2000
    1001
    1016
    1017
    1018
    1999
    2000
    0 0
    
    Expected output
    ABCDEFGHIJKLMNOP 1
    ABCDEFGHIJKLMNOP 16
    abcdefghijklmnop 1
    Unknown
    MixedCaseEraXYZ 1
    MixedCaseEraXYZ 2