Problem:


Problem A: Era Name

As many of you know, we have two major calendar systems used in Japan today. One of them
is Gregorian calendar which is widely used across the world. It is also known as “Western
calendar” in Japan.

The other calendar system is era-based calendar, or so-called “Japanese calendar.” This system
comes from ancient Chinese systems. Recently in Japan it has been a common way to associate
dates with the Emperors. In the era-based system, we represent a year with an era name given
at the time a new Emperor assumes the throne. If the era name is “A”, the first regnal year
will be “A 1”, the second year will be “A 2”, and so forth.

Since we have two different calendar systems, it is often needed to convert the date in one
calendar system to the other. In this problem, you are asked to write a program that converts
western year to era-based year, given a database that contains association between several
western years and era-based years.

For the simplicity, you can assume the following:

   
 A new era always begins on January 1st of the corresponding Gregorian year.

   
 The first year of an era is described as 1.

   
 There is no year in which more than one era switch takes place.

Please note that, however, the database you will see may be incomplete. In other words, some
era that existed in the history may be missing from your data. So you will also have to detect
the cases where you cannot determine exactly which era the given year belongs to.

Input

The input contains multiple test cases. Each test case has the following format:

     N Q

     EraName1 EraBasedYear1 WesternYear1

     .

     .

     .

     EraNameN EraBasedYearN WesternYearN

Query1
.

.

.

QueryQ

The first line of the input contains two positive integers N and Q (1 ≤ N ≤ 1000, 1 ≤ Q ≤ 1000).
N is the number of database entries, and Q is the number of queries.

Each of the following N lines has three components: era name, era-based year number and the
corresponding western year (1 ≤ EraBasedYeari ≤ WesternYeari ≤ 109 ). Each of era names
consist of at most 16 Roman alphabet characters. Then the last Q lines of the input specifies
queries (1 ≤ Queryi ≤ 109 ), each of which is a western year to compute era-based representation.

The end of input is indicated by a line containing two zeros. This line is not part of any dataset
and hence should not be processed.

You can assume that all the western year in the input is positive integers, and that there is no
two entries that share the same era name.

Output

For each query, output in a line the era name and the era-based year number corresponding to
the western year given, separated with a single whitespace. In case you cannot determine the
era, output “Unknown” without quotes.

Sample 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

Output for the Sample Input

meiji 1
taisho 6
Unknown
Unknown



Sample 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


Sample output:
meiji 1
taisho 6
Unknown
Unknown

Submission status: Wrong Answer

Solution code:
inputnum,outputnum = (int(n) for n in input().split(' '))
data = {}
while True:
    for i in range(inputnum):
        temp = input().split(' ')
        data[temp[0]] = [int(temp[2]) - int(temp[1]) + 1,int(temp[2])]
    for o in range(outputnum):
        targ = int(input())
        for k,v in data.items():
            if v[0] <= targ  <= v[1]:
                print(k + ' ' + str(targ-v[0] + 1))
                break
        else:
            print("Unknown")
    inputnum,outputnum = (int(n) for n in input().split(' '))
    if inputnum == outputnum == 0:
        break

Submission status: Accepted

Solution code:
from bisect import bisect_left


while True:
	N, Q = map(int, input().split(' '))
	if N == 0:
		break

	era = {} # Like {1877: ('Meiji', 10)}

	years = [] # 西暦
	for _ in range(N):
		name, j, w = input().split(' ')
		j, w = int(j), int(w)
		era[w] = (name, j)
		years.append(w)
	years.sort()

	for _ in range(Q):
		q = int(input())
		i = bisect_left(years, q)
		if i >= len(years):
			print('Unknown')
			continue
		y = years[i]
		name, length = era[y]
		if q - y + length <= 0:
			print('Unknown')
		else:
			print(name + ' ' + str(q-y+length))

Submission status: Accepted

Solution code:
while 1:
	N, Q = map(int,raw_input().split())
	if (N, Q) == (0,0):
		break
	era = dict()
	for i in range(N):	
		inputs = raw_input().split(" ")
		ename = inputs[0]
		eyear, wyear =map(int,inputs[1:])
		start = wyear - eyear + 1
		if start in era:
			if era[start][1] < wyear:
				era[start][1] = wyear
		else :
			era[start] = [ename, wyear]
	era_list = sorted(era)
	for i in range(Q):
		q = int(raw_input())
		for start in era_list:
			if q <= era[start][1]:
				result = "Unknown" if q < start else "%s %d" % (era[start][0], q - start+1)
				break
		else :
			result = "Unknown"
		print result

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        while True:
            n, q = map(int, raw_input().split())
            if n == q == 0:
                break
            db = []
            for i in range(n):
                en, eby, wy = raw_input().split()
                eby = int(eby)
                wy = int(wy)
                db.append((en, wy - eby + 1, wy))
            db.sort(key=lambda x: x[1])
            for i in range(q):
                y = input()
                for en, s, f in db:
                    if s <= y <= f:
                        print en, y - s + 1
                        break
                else:
                    print 'Unknown'
        
        
        return None

if __name__ == '__main__':
    m = Main()
    m.solve()

Submission status: Accepted

Solution code:
while True:
    N, Q = map(int, input().split())
    if not N:
        break
    a = []
    for i in range(N):
        x, y, z = input().split()
        a.append((int(z), int(z) - int(y), x))
    a = list(reversed(sorted(a)))
    for i in range(Q):
        x = int(input())
        for v in a:
            if v[0] >= x and v[1] < x:
                print(v[2], x - v[1])
                break;
        else:
            print('Unknown')

Submission status: Accepted

Solution code:
#! /usr/bin/python
# -*- coding: utf-8 -*-

def bm_search(dat, q, l, r):
    #print q, l, r
    if l == r:
        if q <= dat[l][2]:
            return int(l)
        else:
            return l+1
    elif q <= dat[l+(r-l)/2][2]:
        return bm_search(dat, q, l, l+(r-l)/2)
    elif dat[l+(r-l)/2][2] < q:
        return bm_search(dat, q, l+(r-l)/2+1, r)

while True:
    (N, Q) = map(int, raw_input().split())
    if N == 0: break
    
    dat = []
    for i in range(N):
        dat.append(raw_input().split())
    for i in range(N):
        dat[i][1] = int(dat[i][1])
        dat[i][2] = int(dat[i][2])
    dat.sort(key = lambda x:x[2])
        
    for i in range(Q):
        q = int(raw_input())
        p = bm_search(dat, q, 0, N-1)
        if p < N and dat[p][1] > dat[p][2]-q:
            print dat[p][0], dat[p][1]-(dat[p][2]-q)
        else:
            print "Unknown"

Submission status: Accepted

Solution code:
inputnum,outputnum = (int(n) for n in input().split(' '))
while True:
    data = {}
    for i in range(inputnum):
        temp = input().split(' ')
        data[temp[0]] = [int(temp[2]) - int(temp[1]) + 1,int(temp[2])]
    for o in range(outputnum):
        targ = int(input())
        for k,v in data.items():
            if v[0] <= targ  <= v[1]:
                print(k + ' ' + str(targ-v[0] + 1))
                break
        else:
            print("Unknown")
    inputnum,outputnum = (int(n) for n in input().split(' '))
    if inputnum == outputnum == 0:
        break

Submission status: Accepted

Solution code:
while 1:
    n,m=map(int,input().split())
    if n==0:break
    e=['']*n;b=['']*n;w=['']*n
    for i in range(n):e[i],b[i],w[i]=input().split()
    b=list(map(int,b));w=list(map(int,w))
    for _ in range(m):
        q=int(input())
        for i in range(n):
            if w[i]-b[i]<q<=w[i]:print(e[i],b[i]-w[i]+q);break
        else:print('Unknown')

Submission status: Accepted

Solution code:
while True:
    n, q = map(int, input().split())
    d = {}

    if n == 0 and q == 0:
        break

    for i in range(n):
        era, years, now = input().split()
        begin = int(now) - int(years) + 1
        d[era] = [begin, int(now)]

    for i in range(q):
        year = int(input())
        for e, y in d.items():
            if year >= y[0] and year <= y[1]:
                print(e, year - y[0] + 1)
                break
        else:
            print('Unknown')

Submission status: Accepted

Solution code:
import bisect
while True:
    N,Q = map(int,input().split())
    if N == 0: break
    src = []
    for i in range(N):
        n,l,y = input().split()
        src.append((int(y), int(l), n))
    src.sort()
    for i in range(Q):
        q = int(input())
        a = bisect.bisect(src,(q,-1,-1))
        if a < N:
            y,l,n = src[a]
            if y-l < q <= y:
                print(n + ' ' + str(q-y+l))
                continue
        if a+1 < N:
            y,l,n = src[a+1]
            if y-l < q <= y:
                print(n + ' ' + str(q-y+l))
                continue
        print('Unknown')

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    dd = [(1,1),(1,0),(0,1),(0,-1),(-1,0),(-1,-1)]

    while True:
        n,q = LI()
        if n == 0 and q == 0:
            break
        a = [LS() for _ in range(n)]
        a = [[_[0],int(_[1]),int(_[2])] for _ in a]
        b = [I() for _ in range(q)]
        for c in b:
            r = 'Unknown'
            for l,e,w in a:
                if w-e < c <= w:
                    r = '{} {}'.format(l, e-w+c)
            rr.append(r)

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
import sys
import bisect

while True:
    n, m = map(int, sys.stdin.readline().split())
    if n == 0:
        break
    date = []
    for i in xrange(n):
        input = raw_input().split()
        name = input[0]
        end = int(input[2])
        start = end - int(input[1]) + 1
        date.append((start, end, name))
    for i in xrange(m):
        year = int(raw_input())
        for j in date:
            if j[0] <= year <= j[1]:
                print j[2], year - j[0] + 1
                break
        else:
            print 'Unknown'

Submission status: Accepted

Solution code:
while True:
    N,Q=map(int,raw_input().split())
    if N==Q==0:break
    L=[]
    for	i in range(N):
	en,eby,wy=raw_input().split()
	L.append((int(wy)-int(eby)+1,int(wy),en))
    L.sort()
    for	i in range(Q):
	q=input()
	for j in range(N):
            if L[j][0]<=q<=L[j][1]:
		print L[j][2],q-L[j][0]+1
		break
        else:
            print "Unknown"

Submission status: Accepted

Solution code:
while 1:
	n,m = map(int,raw_input().split())
	if n == 0: break
	EBY = [raw_input().split() for i in range(n)]
	EBY = [[e,int(b),int(y)] for e,b,y in EBY]
	for i in range(m):
		year = int(raw_input())
		for j in range(n):
			if EBY[j][2]-EBY[j][1] < year <= EBY[j][2]:
				print EBY[j][0], year-EBY[j][2]+EBY[j][1]
				break
		else:
			print "Unknown"

Submission status: Accepted

Solution code:
while 1:
	n,m = map(int,raw_input().split())
	if n == 0: break
	EBY = [raw_input().split() for i in range(n)]
	EBY = [[e,int(y)-int(b),int(y)] for e,b,y in EBY]
	for i in range(m):
		year = int(raw_input())
		for j in range(n):
			if EBY[j][1] < year <= EBY[j][2]:
				print EBY[j][0], year-EBY[j][1]
				break
		else:
			print "Unknown"

Submission status: Accepted

Solution code:
#Time limit exceedsになるので二分探索法を使う
from bisect import bisect_left


while True:
    n, q = map(int, input().split())
    if n == 0:
        break

    era = {} # {西暦: ('元号', 年)}
    years = [] 
    
    for _ in range(n):
        gengou, wa_year, we_year = input().split()
        wa_year = int(wa_year)
        we_year = int(we_year)
        era[we_year] = (gengou, wa_year)
        years.append(we_year)
    
    years_final = sorted(years) 

    for _ in range(q):
        year1 = int(input())
        temp = bisect_left(years_final, year1)
        
        if temp >= len(years_final):
            print('Unknown')
            continue
            
        year2 = years_final[temp]
        gengou, span = era[year2]
        result = year1 - year2 + span

        if result <= 0:
            print('Unknown')
        else:
            print(gengou, result)

Submission status: Accepted

Solution code:
while True:
  Name=[]
  first=[]
  final=[]
  N,Q =map(int,input().split())
  if N==Q==0:
    break
  else:
    for n in range(N):
      eraname,erabasedyear,westernyear=input().split()
      Name.append(eraname)
      era_first=int(westernyear) - int(erabasedyear) +1
      first.append(int(era_first))
      final.append(int(westernyear))
    for q in range(Q):
        year=int(input())
        count=0
        for n in range(N):
          if first[n] <= year <=final[n]:
            era_year = year -first[n] +1
            print(Name[n],era_year)
            count+=1
        if count==0:
          print("Unknown")

Submission status: Accepted

Solution code:
while True:
    inp,oup=map(int,input().split())
    if not inp: 
        break
    dic={}
    for i in range(inp):
        era,num,wes=input().split()
        dic[era] =[int(wes)-int(num)+1, int(wes)]
    for j in range(oup):
        p=int(input())
        for i in dic:
            if dic[i][0]<=p<=dic[i][1]:
                print(i+' '+str(p-dic[i][0]+1))
                break
        else:
             print('Unknown')

Submission status: Accepted

Solution code:
while True:
    n,m= map(int,input().split())
    if n==0 and m==0:
        break
    hajime= {}
    owari= {}
    for _ in range(n):
        a,b,c= input().split()
        hajime[a]= int(c)- int(b)
        owari[a]= int(c)

    for _ in range(m):
        year= int(input())
        for a in hajime:
            flag= True
            if hajime[a]< year and year<= owari[a]:
                flag= False
                print(a,year- hajime[a])
                break
        if flag:
            print("Unknown")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def solve(N,Q):
    era = []
    for _ in range(N):
        X = input().split()
        name = X[0]
        y = int(X[1])
        w = int(X[2])
        era.append((w - y + 1,w,name))

    for _ in range(Q):
        flag = False
        y = int(input())
        for a,b,c in era:
            if a <= y <= b:
                flag = True
                ans = (c,y - a + 1)
                break
        if flag:
            print(*ans)
        else:
            print('Unknown')

def main():
    while True:
        N,Q = map(int,input().split())
        if N == 0:
            return
        solve(N,Q)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve(n,e,q):
    l = set([i for i in q])
    d = defaultdict(lambda : 0)
    for i in range(n):
        n,j,k = e[i]
        j = int(j)
        k = int(k)
        d[k-j+1] += i+1
        d[k+1] -= i+1
        l.add(k-j+1)
        l.add(k+1)
    l = list(l)
    l.sort()
    for i in range(len(l)-1):
        d[l[i+1]] += d[l[i]]
    for i in q:
        j = d[i]
        if j > 0:
            print(e[j-1][0],i-int(e[j-1][2])+int(e[j-1][1]))
        else:
            print("Unknown")
    return

#Solve
if __name__ == "__main__":
    while 1:
        n,Q = LI()
        if n == Q == 0:
            break
        e = [input().split() for i in range(n)]
        q = IR(Q)
        solve(n,e,q)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left


while True:
	N, Q = map(int, input().split(' '))
	if N == 0:
		break

	era = {} # Like {1877: ('Meiji', 10)}

	years = [] # 西暦
	for _ in range(N):
		name, j, w = input().split(' ')
		j, w = int(j), int(w)
		era[w] = (name, j)
		years.append(w)
	years.sort()

	for _ in range(Q):
		q = int(input())
		y = years[bisect_left(years, q)]
		name, length = era[y]
		if q - y + length <= 0:
			print('Unknown')
		else:
			print(name + ' ' + str(q-y+length))

Submission status: Runtime Error

Solution code:
while 1:
	n,m = map(int,raw_input().split())
	if n == 0: break
	E,B,Y = [],[],[]
	for i in range(n):
		era,base,year = raw_input().split()
		E.append(era)
		B.append(int(base))
		Y.append(int(year))
	for i in range(m):
		year = int(raw_input())
		for j in range(n):
			if Y[j]-B[j] < year <= Y[j]:
				print E[i], year-Y[j]+B[i]
				break
		else:
			print "Unknown"

Submission status: Runtime Error

Solution code:
while 1:
	n,m = map(int,raw_input().split())
	if n == 0: break
	E,B,Y = [],[],[]
	for i in range(n):
		era,base,year = raw_input().split()
		E.append(era)
		B.append(int(base))
		Y.append(int(year))
	for i in range(m):
		year = int(raw_input())
		for j in range(n):
			if Y[j]-B[j] < year <= Y[j]:
				print E[i], year-Y[j]+B[j]
				break
		else:
			print "Unknown"