Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

A *time* is a string in the format "HH:MM AM" or "HH:MM PM" (without quotes), where HH and MM are always two-digit numbers. A day starts at 12:00 AM and ends at 11:59 PM. You may refer [here] for understanding the 12-hour clock format.

Chef has scheduled a meeting with his friends at a time $P$. He has $N$ friends (numbered $1$ through $N$); for each valid $i$, the $i$-th friend is available from a time $L_{i}$ to a time $R_{i}$ (both inclusive). For each friend, can you help Chef find out if this friend will be able to attend the meeting? More formally, check if $L_{i} ≤ P ≤ R_{i}$ for each valid $i$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single time $P$.
The second line contains a single integer $N$.
$N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated times $L_{i}$ and $R_{i}$.

------  Output ------
For each test case, print a single line containing one string with length $N$. For each valid $i$, the $i$-th character of this string should be '1' if $i$-th friend will be able to attend the meeting or '0' otherwise. 

------  Constraints  ------
$1 ≤ T ≤ 500$
$1 ≤ N ≤ 500$
each time is valid in the 12-hour clock format
for each valid $i$, the time $R_{i}$ is greater or equal to $L_{i}$

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
2

12:01 AM

4

12:00 AM 11:42 PM

12:01 AM 11:59 AM

12:30 AM 12:00 PM

11:59 AM 11:59 PM

04:12 PM

5

12:00 AM 11:59 PM

01:00 PM 04:12 PM

04:12 PM 04:12 PM

04:12 AM 04:12 AM

12:00 PM 11:59 PM
----- Sample Output 1 ------ 
1100

11101
----- explanation 1 ------ 
Example case 1: 
- Friend $1$: 12:01 AM lies between 12:00 AM and 11:42 PM (that is, between 00:00 and 23:42 in the 24-hour clock format), so this friend will be able to attend the meeting.
- Friend $2$: 12:01 AM lies between 12:01 AM and 11:59 AM (between 00:01 and 11:59 in the 24-hour clock format).
- Friend $3$: 12:01 AM does not lie between 12:30 AM and 12:30 PM (between 00:30 and 12:30 in the 24-hour clock format), so this friend will not be able to attend the meeting.
- Friend $4$: 12:01 AM does not lie between 11:59 AM and 11:59 PM (between 11:59 and 23:59 in the 24-hour clock format).

Example case 2: For friend $3$, 04:12 PM lies between 04:12 PM and 04:12 PM (inclusive) and hence this friend will be able to attend the meeting.

Difficulty: MEDIUM
Tags: Constructive algorithms

String algorithms

Implementation

Mathematics

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
def min_conversion(p, h, m):
	if p == 'PM':
		if h != 12:
			h += 12
	elif h == 12:
		h -= 12
	res = h * 60 + m
	return res
for _ in range(int(input())):
	q = input()
	x = q[-2:]
	t0 = q[:-3]
	(h0, m0) = map(int, t0.split(':'))
	final_t = min_conversion(x, h0, m0)
	n = int(input())
	for i in range(n):
		inn = input()
		(a, b) = (inn[:8], inn[8:])
		(d, e) = (a[-2:], b[-2:])
		(t1, t2) = (a[:-3], b[:-3])
		(h1, m1) = map(int, t1.split(':'))
		(h2, m2) = map(int, t2.split(':'))
		final_mins1 = min_conversion(d, h1, m1)
		final_mins2 = min_conversion(e, h2, m2)
		if final_mins1 <= final_t <= final_mins2:
			print(1, end='')
		else:
			print(0, end='')
	print()


def conv(t):
	tod = t[-2:]
	t = t[:-3]
	(h, m) = map(int, t.split(':'))
	ans = 0
	if tod == 'PM':
		if h != 12:
			h += 12
	elif h == 12:
		h -= 12
	ans = h * 60 + m
	return ans
for _ in range(int(input())):
	chef = conv(input())
	for i in range(int(input())):
		ra = input()
		(st, en) = (conv(ra[:8]), conv(ra[8:]))
		if st <= chef <= en:
			print(1, end='')
		else:
			print(0, end='')
	print()


def time_conv(i):
	(hour, mins) = i.split(':')
	total = int(hour[:2]) * 60 + int(mins[:2])
	if hour[:2] == '12':
		if i[-2:] == 'AM':
			total -= 12 * 60
	elif i[-2:] == 'PM':
		total += 12 * 60
	return total

def can_meet(start, end, meet):
	(start, end) = (time_conv(start), time_conv(end))
	if start <= meet <= end:
		return '1'
	else:
		return '0'
for t in range(int(input())):
	meet = time_conv(input())
	make = ''
	for n in range(int(input())):
		(start, end) = input().replace(' ', '', 1).split(' ', 1)
		make += can_meet(start, end, meet)
	print(make)


t = int(input())
a = str()
for _ in range(t):
	p = input()
	u = p[-2:]
	h = p[:2]
	m = p[3:5]
	if u == 'AM':
		if h == '12':
			meet = int(m)
		else:
			meet = int(h) * 60 + int(m)
	elif h == '12':
		meet = int(m) + 12 * 60
	else:
		meet = int(h) * 60 + int(m) + 12 * 60
	n = int(input())
	for i in range(n):
		b = input()
		l = b[:8]
		r = b[9:]
		v1 = l[-2:]
		v2 = r[-2:]
		j1 = l[:2]
		j2 = r[:2]
		k1 = l[3:5]
		k2 = r[3:5]
		if v1 == 'AM':
			if j1 == '12':
				meet1 = int(k1)
			else:
				meet1 = int(j1) * 60 + int(k1)
		elif j1 == '12':
			meet1 = int(k1) + 12 * 60
		else:
			meet1 = int(j1) * 60 + int(k1) + 12 * 60
		if v2 == 'AM':
			if j2 == '12':
				meet2 = int(k2)
			else:
				meet2 = int(j2) * 60 + int(k2)
		elif j2 == '12':
			meet2 = int(k2) + 12 * 60
		else:
			meet2 = int(j2) * 60 + int(k2) + 12 * 60
		if meet1 <= meet and meet <= meet2:
			a += '1'
		else:
			a += '0'
	print(a)
	a = str()


def time(k):
	h = int(k[0:2])
	m = int(k[3:5])
	r = k[-2:]
	if h == 12:
		h = h - 12
	if r == 'PM':
		h = h + 12
	return h * 60 + m
for i in range(int(input())):
	a = time(input())
	b = int(input())
	empty = ''
	for j in range(b):
		c = input().split()
		(k1, k2) = (time(''.join(c[:2])), time(''.join(c[-2:])))
		if k1 <= a <= k2:
			empty += '1'
		else:
			empty += '0'
	print(empty)


g = int(input())
for i in range(g):
	t = input()
	t = t.split()
	t0 = t[0].split(':')
	t1 = int(t0[0])
	t2 = int(t0[1])
	s = t[1]
	if s == 'AM' and t1 == 12:
		t1 = 0
	elif s == 'PM' and t1 != 12:
		t1 += 12
	c = 0
	for j in range(int(input())):
		a = input()
		a = a.split()
		a0 = a[0].split(':')
		a1 = int(a0[0])
		a2 = int(a0[1])
		s1 = a[1]
		b0 = a[2].split(':')
		b1 = int(b0[0])
		b2 = int(b0[1])
		s2 = a[3]
		if s1 == 'AM' and a1 == 12:
			a1 = 0
		elif s1 == 'PM' and a1 != 12:
			a1 += 12
		if s2 == 'AM' and b1 == 12:
			b1 = 0
		elif s2 == 'PM' and b1 != 12:
			b1 += 12
		ans1 = t1 - a1
		ans2 = t2 - a2
		ans3 = b1 - t1
		ans4 = b2 - t2
		if ans1 < 0 or ans3 < 0:
			print(0, end='')
		elif ans1 > 0 and ans3 > 0:
			print(1, end='')
		elif ans1 > 0 and ans3 == 0:
			if ans4 >= 0:
				print(1, end='')
			else:
				print(0, end='')
		elif ans1 == 0 and ans3 > 0:
			if ans2 >= 0:
				print(1, end='')
			else:
				print(0, end='')
		elif ans1 == 0 and ans3 == 0:
			if ans2 >= 0 and ans4 >= 0:
				print(1, end='')
			else:
				print(0, end='')
	g = g - 1
	print()


def tim(tr):
	er = [111, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0]
	if tr[6:] == 'AM':
		y = er[int(tr[:2])] * 60 + int(tr[3:5])
		return y
	else:
		y = er[int(tr[:2])] * 60 + int(tr[3:5]) + 12 * 60
		return y
for _ in range(int(input())):
	p = input()
	n = int(input())
	f = []
	for i in range(n):
		r = input()
		f.append(r)
	pp = tim(p)
	h = ''
	for j in range(n):
		up = tim(f[j][9:])
		low = tim(f[j][:8])
		if low <= pp:
			if low <= up and pp <= up:
				h = h + '1'
			elif up < low and up < pp:
				h = h + '1'
			else:
				h = h + '0'
		else:
			h = h + '0'
	print(h)


t = int(input())
for test_case in range(0, t):
	(pa, pb) = list(input().split())
	friend_num = int(input())
	(h, m) = map(int, pa.split(':'))
	p_time = 0
	if pb == 'PM':
		if h != 12:
			p_time = 60 * (h + 12) + m
		else:
			p_time = 60 * h + m
	elif h != 12:
		p_time = 60 * h + m
	else:
		p_time = m
	timings = []
	for i in range(0, friend_num):
		(a, b, c, d) = input().split()
		(h1, m1) = map(int, a.split(':'))
		if b == 'PM':
			if h1 != 12:
				start_time = 60 * (h1 + 12) + m1
			else:
				start_time = 60 * h1 + m1
		elif h1 != 12:
			start_time = 60 * h1 + m1
		else:
			start_time = m1
		(h2, m2) = map(int, c.split(':'))
		if d == 'PM':
			if h2 != 12:
				end_time = 60 * (h2 + 12) + m2
			else:
				end_time = 60 * h2 + m2
		elif h2 != 12:
			end_time = 60 * h2 + m2
		else:
			end_time = m2
		timings.append((start_time, end_time))
	solution_string = ''
	for (x, y) in timings:
		if p_time >= x and p_time <= y:
			solution_string += '1'
		else:
			solution_string += '0'
	print(solution_string)


def conv(i):
	(h, m) = i.split(':')
	t = int(h[:2]) * 60 + int(m[:2])
	if h[:2] == '12':
		if i[-2:] == 'AM':
			t -= 12 * 60
	elif i[-2:] == 'PM':
		t += 12 * 60
	return t

def cm(s, e, m):
	(s, e) = (conv(s), conv(e))
	if s <= m <= e:
		return '1'
	else:
		return '0'
T = int(input())
for x in range(T):
	me = conv(input())
	m = ''
	for n in range(int(input())):
		(s, e) = input().replace(' ', '', 1).split(' ', 1)
		m += cm(s, e, me)
	print(m)


def to_24(time):
	ap = time[-2:]
	hrs = int(time[:2])
	mins = int(time[3:5])
	if ap == 'PM' and hrs != 12:
		hrs += 12
	elif ap == 'AM' and hrs == 12:
		hrs = 0
	return hrs * 100 + mins

def soln(p, n, times):
	res = ''
	p = to_24(p)
	for i in range(n):
		if to_24(times[i][0]) <= p <= to_24(times[i][1]):
			res += '1'
		else:
			res += '0'
	return res
for _ in range(int(input())):
	p = input()
	n = int(input())
	conv = lambda x: [x[0] + x[1], x[2] + x[3]]
	times = [conv(input().split()) for i in range(n)]
	print(soln(p, n, times))


tests = int(input())

def getTimeVal(string, time_period):
	(hours, minutes) = string.strip().split(':')
	ans = int(hours) % 12 * 60 + int(minutes)
	if time_period == 'PM':
		ans += 720
	return ans
for i in range(tests):
	meetingAt = input().strip().split(' ')
	meetingTimeVal = getTimeVal(meetingAt[0], meetingAt[1])
	friends = int(input())
	ans = ''
	for j in range(friends):
		availbility = input().strip().split(' ')
		availableFrom = getTimeVal(availbility[0], availbility[1])
		availableTill = getTimeVal(availbility[2], availbility[3])
		if availableFrom <= meetingTimeVal <= availableTill:
			ans += '1'
		else:
			ans += '0'
	print(ans)


def tconverter(s):
	if s[-2:] == 'AM' and s[:2] == '12':
		s = '00' + s[2:-2]
	elif s[-2:] == 'AM':
		s = s[:-2]
	elif s[-2:] == 'PM' and s[:2] == '12':
		s = s[:-2]
	else:
		s = str(int(s[:2]) + 12) + s[2:-2]
	return int(s[0] + s[1]) * 60 + int(s[3] + s[4])
for i in range(int(input())):
	x = tconverter(input())
	n = int(input())
	s = ''
	for i in range(n):
		y = input()
		y1 = tconverter(y[0:8])
		y2 = tconverter(y[9:])
		if x >= y1 and x <= y2 or (x >= y2 and x <= y1):
			s += '1'
		else:
			s += '0'
	print(s)


def convert(n1, n2):
	n1 = n1.replace(':', '.')
	n1 = float(n1)
	if n1 >= 12:
		n1 -= 12
	if n2 == 'PM':
		n1 += 12
	return n1
for _ in range(int(input())):
	n = input()
	(n1, n2) = map(str, n.split())
	n1 = convert(n1, n2)
	string = ''
	for i in range(int(input())):
		s = input()
		(L1, L2, R1, R2) = map(str, s.split())
		Li1 = convert(L1, L2)
		Ri1 = convert(R1, R2)
		if Li1 <= n1 <= Ri1:
			string += '1'
		else:
			string += '0'
	print(string)


for z in range(int(input())):
	p = input().split()
	b = [False]
	if p[1] == 'PM':
		b[0] = True
	n = int(input())
	a = []
	for i in range(n):
		a.append(input().split())

	def comp(x):
		if b[0] and x[1] == 'AM':
			return True
		if not b[0] and x[1] == 'PM':
			return False
		h1 = int(p[0][:2])
		m1 = int(p[0][3:])
		h2 = int(x[0][:2])
		m2 = int(x[0][3:])
		if h1 == 12:
			h1 -= 12
		if h2 == 12:
			h2 -= 12
		if h1 > h2 or (h1 == h2 and m1 >= m2):
			return True
		return False
	r = []
	for i in range(n):
		if comp(a[i][:2]) and (not comp(a[i][2:]) or a[i][2:] == p):
			r.append('1')
		else:
			r.append('0')
	print(''.join(r))


def convert_24(time):
	P = str(time).split(' ')
	P24 = ''
	x = str(P[0]).split(':')
	if P[1] == 'AM':
		if int(x[0]) == 12:
			P24 = int('00' + x[1])
		else:
			P24 = int(str(int(x[0])) + x[1])
	elif int(x[0]) == 12:
		P24 = int(str(int(x[0])) + x[1])
	else:
		P24 = int(str(int(x[0]) + 12) + x[1])
	return P24
T = int(input())
for t in range(T):
	P = convert_24(input())
	N = int(input())
	L = []
	R = []
	for n in range(N):
		x = str(input()).split(' ')
		L_str = x[0] + ' ' + x[1]
		R_str = x[2] + ' ' + x[3]
		L.append(convert_24(L_str))
		R.append(convert_24(R_str))
	output = ''
	for index in range(N):
		if R[index] < L[index]:
			R[index] += 2400
		if L[index] <= P and P <= R[index]:
			output += '1'
		else:
			output += '0'
	print(output)


for _ in range(int(input())):
	p = input()
	ph = int(p[:2])
	pm = int(p[3:5])
	pp = p[-2:]
	if pp == 'PM':
		pm += 720
	if ph != 12:
		pm += ph * 60
	n = int(input())
	s = ''
	for _ in range(n):
		t = input()
		(t1, t2) = (t[:9], t[9:])
		t1h = int(t1[:2])
		t1m = int(t1[3:5])
		t1p = t1[6:8]
		if t1p == 'PM':
			t1m += 720
		if t1h != 12:
			t1m += t1h * 60
		t2h = int(t2[:2])
		t2m = int(t2[3:5])
		t2p = t2[-2:]
		if t2p == 'PM':
			t2m += 720
		if t2h != 12:
			t2m += t2h * 60
		if t1m <= pm <= t2m:
			s += '1'
		else:
			s += '0'
	print(s)


t = int(input())
for i in range(t):
	s = input()
	h = int(s[:2])
	m = int(s[3:5])
	p = s[-2:]
	if p == 'PM':
		m += 720
	if h != 12:
		m += 60 * h
	n = int(input())
	u = ''
	for j in range(n):
		q = input()
		(q1, q2) = (q[:9], q[9:])
		h1 = int(q1[:2])
		m1 = int(q1[3:5])
		p1 = q1[6:8]
		if p1 == 'PM':
			m1 += 720
		if h1 != 12:
			m1 += 60 * h1
		h2 = int(q2[:2])
		m2 = int(q2[3:5])
		p2 = q2[6:8]
		if p2 == 'PM':
			m2 += 720
		if h2 != 12:
			m2 += 60 * h2
		if m1 <= m <= m2:
			u += '1'
		else:
			u += '0'
	print(u)


def time_chenger(strr, addi):
	hour = strr[0:2]
	if addi == 1 and strr[-2] == 'A':
		hour = str(int(hour) + 24)
	minute = strr[3:5]
	am_pm = strr[-2]
	if hour == '12':
		hour = '00'
	if am_pm == 'P':
		hour = str(int(hour) + 12)
	time = hour + minute
	return time
t = int(input())
for i in range(t):
	x = input()
	addi = 0
	time_x = time_chenger(x, addi)
	time_x1 = time_chenger(x, 1)
	n = int(input())
	for j in range(n):
		y = input()
		a = y[:8]
		b = y[9:]
		if a[-2] == 'P' and a[-2] == 'A':
			addi = 1
		time_a = time_chenger(a, addi)
		time_b = time_chenger(b, addi)
		if time_a <= time_x and time_b >= time_x:
			print(1, end='')
		elif time_a <= time_x1 and time_b >= time_x1:
			print(1, end='')
		else:
			print(0, end='')
		addi = 0
	print()


def convert_time(x, a):
	(hr, mi) = list(x.split(':'))
	if a == 'AM' and hr == '12':
		hr = '00'
	elif a == 'PM':
		hr = str(int(hr) + 12)
		if hr == '24':
			hr = '12'
	return str(hr) + ':' + str(mi)
T = int(input())
for _ in range(T):
	(Base_time, a) = list(input().split())
	Base_time = convert_time(Base_time, a)
	sub_t = int(input())
	out = []
	for _ in range(sub_t):
		(x, a, y, b) = list(input().split())
		x = convert_time(x, a)
		y = convert_time(y, b)
		if x <= Base_time and Base_time <= y:
			out.append('1')
		else:
			out.append('0')
	print(''.join(out))


import datetime

def conTime(tt):
	s = list(str(tt).split())
	t = str(s[0]).split(':')
	if s[1] == 'AM':
		if int(t[0]) == 12:
			t[0] = 0
	else:
		if int(t[0]) == 12:
			t[0] = 0
		t[0] = int(t[0]) + 12
	now = datetime.datetime.now()
	return now.replace(hour=int(t[0]), minute=int(t[1]), second=0, microsecond=0)
for _ in range(int(input())):
	s = input()
	t1 = conTime(s)
	ans = ''
	for _ in range(int(input())):
		k = list(input().split())
		r_time = conTime(str(k[0]) + ' ' + str(k[1]))
		l_time = conTime(str(k[2]) + ' ' + str(k[3]))
		if r_time <= t1 and t1 <= l_time:
			ans += '1'
		else:
			ans += '0'
	print(ans)


def change(p):
	str1 = ''
	if p[6] == 'P':
		str1 += '1'
	else:
		str1 += '0'
	if p[0:2] == '12':
		str1 += '00'
	else:
		str1 += p[0:2]
	str1 += p[3:5]
	return int(str1)

def compare(a, b, c):
	if a <= c <= b:
		return '1'
	return '0'
for i in range(int(input())):
	p = input()
	p_new = change(p)
	n = int(input())
	result = ''
	for i in range(n):
		time = input()
		li = time[:9]
		ri = time[9:]
		newli = change(li)
		newri = change(ri)
		result += compare(newli, newri, p_new)
	print(result)


try:

	def convert(p):
		pm = 0
		if p[0] == '1' and p[1] == '2':
			if p[6] == 'P':
				pm += 720 + int(p[3] + p[4])
			else:
				pm += int(p[3] + p[4])
			return pm
		pm = int(p[0:2]) * 60 + int(p[3] + p[4])
		if p[6] == 'P':
			pm += 720
		return pm
	t = int(input())
	for i in range(t):
		p = input()
		pm = convert(p)
		n = int(input())
		s = ''
		for j in range(n):
			l = input()
			(l, r) = (l[0:8], l[9:])
			lm = convert(l)
			rm = convert(r)
			if lm <= pm and rm >= pm:
				s += '1'
			else:
				s += '0'
		print(s)
except:
	pass


def actual_time(n):
	m = int(n[:2] + n[3:5])
	if 'PM' in n and m < 1200:
		m = m + 1200
	if 'AM' in n and m >= 1200:
		m = m - 1200
	return m
t = int(input())
for i in range(t):
	p = input()
	p = actual_time(p)
	n = int(input())
	ans = ''
	for i in range(n):
		s = input()
		l = s[:8]
		r = s[9:]
		l = actual_time(l)
		r = actual_time(r)
		if l <= p <= r:
			ans = ans + '1'
		else:
			ans = ans + '0'
	print(ans)


def chef(n12):
	m11 = int(n12[:2] + n12[3:5])
	if 'PM' in n12 and m11 < 1200:
		m11 = m11 + 1200
	if 'AM' in n12 and m11 >= 1200:
		m11 = m11 - 1200
	return m11
for a1 in range(int(input())):
	v = input()
	n12 = chef(v)
	add = ''
	for i23 in range(int(input())):
		p23 = input()
		f34 = chef(p23[:8])
		f12 = chef(p23[9:])
		if f34 <= n12 <= f12:
			add += '1'
		else:
			add += '0'
	print(add)


import sys
input = sys.stdin.readline

def rii():
	return range(int(input().strip()))

def ii():
	return int(input().strip())

def mii():
	return map(int, input().strip().split(' '))

def lmii():
	return list(map(int, input().strip().split(' ')))

def si():
	return str(input().strip())
import re
regex = '^([0-1][0-9]):([0-5][0-9])\\s(AM|PM)$'

class Time:

	def __init__(self, timestring):
		r = re.findall(regex, timestring)[0]
		(h, m) = map(int, r[:2])
		h %= 12
		h += 12 if r[2] == 'PM' else 0
		self.t = h * 60 + m

	def __le__(self, other):
		return self.t <= other.t

	def __ge__(self, other):
		return self.t >= other.t

def solve(*args):
	(chef, friends) = args
	outp = ''
	for f in friends:
		outp += '1' if all([chef >= f[0], chef <= f[1]]) else '0'
	return outp

def do_codechef():
	for t in rii():
		chef = Time(si())
		n = ii()
		friends = list()
		for _ in range(n):
			(ft, fap, tt, tap) = si().split(' ')
			friends.append((Time(ft + ' ' + fap), Time(tt + ' ' + tap)))
		print(solve(chef, friends))
do_codechef()
exit()


def chef(n):
	m = int(n[:2] + n[3:5])
	if 'PM' in n and m < 1200:
		m = m + 1200
	if 'AM' in n and m >= 1200:
		m = m - 1200
	return m
for x in range(int(input())):
	n = chef(input())
	add = ''
	for i in range(int(input())):
		r = input()
		l = chef(r[:8])
		f = chef(r[9:])
		if l <= n <= f:
			add += '1'
		else:
			add += '0'
	print(add)


def con(t, d):
	hrs = int(t[:2])
	if d[0] == 'A':
		if hrs == 12:
			hrs = 0
	elif hrs != 12:
		hrs += 13
	mins = hrs * 60 + int(t[3:])
	return mins
t = int(input())
for _ in range(t):
	time = input().split()
	mins = con(time[0], time[1])
	q = int(input())
	for __ in range(q):
		time = input().split()
		l = con(time[0], time[1])
		r = con(time[2], time[3])
		if mins >= l and mins <= r:
			print('1', end='')
		else:
			print('0', end='')
	print('')


def convert(time):
	m = int(time[:2] + time[3:5])
	if 'PM' in time and m < 1200:
		m = m + 1200
	if 'AM' in time and m >= 1200:
		m = m - 1200
	return m
t = int(input())
for _ in range(t):
	p = convert(input())
	n = int(input())
	ans = ''
	for z in range(n):
		time = input()
		l = convert(time[:8])
		r = convert(time[9:])
		if l <= p <= r:
			ans = ans + '1'
		else:
			ans = ans + '0'
	print(ans)


def xyz(s):
	a = int(s[0:2])
	b = int(s[3:5])
	c = s[6:8]
	if c == 'AM':
		if a == 12:
			return 0 + b
		else:
			return a * 60 + b
	elif a == 12:
		return a * 60 + b
	else:
		return (a + 12) * 60 + b
for _ in range(int(input())):
	p = input()
	c = xyz(p)
	res = ''
	for i in range(int(input())):
		s = input()
		a = s[:8]
		b = s[9:]
		if xyz(a) <= c and c <= xyz(b):
			res = res + '1'
		else:
			res = res + '0'
	print(res)


def convert(time, ampm):
	(h, m) = time.split(':')
	if h == '12':
		h = '00'
	if ampm == 'PM':
		h = str(12 + int(h))
	return h + m
t = int(input())
for i in range(t):
	P = input().split(' ')
	P = convert(P[0], P[1])
	n = int(input())
	for j in range(n):
		l = [0, 0]
		r = [0, 0]
		(l[0], l[1], r[0], r[1]) = input().split(' ')
		L = convert(l[0], l[1])
		R = convert(r[0], r[1])
		if P >= L and P <= R:
			print('1', end='')
		else:
			print('0', end='')
	print()


def hello(a):
	b = a.split()
	c = b[0]
	b = b[1]
	(c, d) = map(int, c.split(':'))
	if b == 'AM' and c == 12:
		c = 0
	elif b == 'PM' and c != 12:
		c += 12
	return c * 60 + d
for _ in range(int(input())):
	a = hello(input())
	for i in range(int(input())):
		b = input()
		(b, c) = (hello(b[:8]), hello(b[9:]))
		if a in range(b, c + 1):
			print(1, end='')
		else:
			print(0, end='')
	print()


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)

def convert(s):
	t = 0
	if s[-2:] == 'PM':
		t += 12 * 60
	s = s[:-2]
	l1 = s.replace(' ', '').split(':')
	t += int(l1[0]) % 12 * 60 + int(l1[1])
	return t
for _ in range(int(input())):
	p1 = convert(input())
	n = int(input())
	for i in range(n):
		s = input()
		l1 = convert(s[:s.index('M') + 1])
		r1 = convert(s[s.index('M') + 2:])
		if l1 <= p1 <= r1:
			print(1, end='')
		else:
			print(0, end='')
	print()


def time_convert(n):
	time = int(n[0:2] + n[3:5])
	if n[6:8] == 'PM' and time < 1200:
		time = time + 1200
	elif n[6:8] == 'AM' and time >= 1200:
		time = time - 1200
	return time
T = int(input())
for i in range(T):
	P = time_convert(input())
	N = int(input())
	result = ''
	for j in range(N):
		temp = input()
		L = time_convert(temp[0:8])
		R = time_convert(temp[9:17])
		if P >= L and P <= R:
			result += '1'
		else:
			result += '0'
	print(result)


for _ in range(int(input())):
	p = input()
	if p[-2] == 'A':
		if int(p[0:2]) == 12:
			t = int(p[3:5])
		else:
			t = int(p[0:2]) * 60 + int(p[3:5])
	elif int(p[0:2]) == 12:
		t = int(p[3:5]) + 720
	else:
		t = int(p[0:2]) * 60 + int(p[3:5]) + 720
	n = int(input())
	for _ in range(n):
		g = input()
		if g[6] == 'A':
			if int(g[0:2]) == 12:
				t1 = int(g[3:5])
			else:
				t1 = int(g[0:2]) * 60 + int(g[3:5])
		elif g[6] == 'P':
			if int(g[0:2]) == 12:
				t1 = int(g[3:5]) + 720
			else:
				t1 = int(g[0:2]) * 60 + int(g[3:5]) + 720
		if g[-2] == 'A':
			if int(g[9:11]) == 12:
				t2 = int(g[12:14])
			else:
				t2 = int(g[9:11]) * 60 + int(g[12:14])
		elif g[-2] == 'P':
			if int(g[9:11]) == 12:
				t2 = int(g[12:14]) + 720
			else:
				t2 = int(g[9:11]) * 60 + int(g[12:14]) + 720
		if t1 <= t <= t2:
			print(1, end='')
		else:
			print(0, end='')
	print()


from datetime import *
for _ in range(int(input())):
	p = input()
	P = datetime.strptime(p, '%I:%M %p')
	ans = ''
	for i in range(int(input())):
		n = input()
		L = datetime.strptime(n[:8], '%I:%M %p')
		R = datetime.strptime(n[9:], '%I:%M %p')
		if P >= L and P <= R:
			ans = ans + '1'
		else:
			ans = ans + '0'
	print(ans)


tc = int(input())

def time_conv(t):
	n = int(t[:2] + t[3:5])
	if 'PM' in t and n < 1200:
		n += 1200
	elif 'AM' in t and n >= 1200:
		n -= 1200
	return n
for _ in range(tc):
	p = time_conv(input())
	n = int(input())
	T = [input() for _ in range(n)]
	res = ''
	for s in T:
		l = time_conv(s[:8])
		r = time_conv(s[9:])
		if l <= p <= r:
			res += '1'
		else:
			res += '0'
	print(res)


t = int(input())
for i in range(t):
	z = list(input().split(' '))
	(l, m) = map(int, z[0].split(':'))
	if z[1] == 'PM':
		if l != 12:
			l = l + 12
	elif l == 12:
		l = 0
	k = []
	n = int(input())
	for j in range(n):
		c = []
		s = []
		a = list(input().split(' '))
		(d, e) = map(int, a[0].split(':'))
		(h, g) = map(int, a[2].split(':'))
		if a[1] == 'PM':
			if d != 12:
				d = d + 12
		elif d == 12:
			d = 0
		if a[3] == 'PM':
			if h != 12:
				h = h + 12
		elif h == 12:
			h = 0
		if l > d and l < h:
			k.append(1)
		elif l == d and l < h:
			if m >= e:
				k.append(1)
			else:
				k.append(0)
		elif l == d and l == h:
			if m >= e and m <= g:
				k.append(1)
			else:
				k.append(0)
		elif l > d and l == h:
			if m <= g:
				k.append(1)
			else:
				k.append(0)
		else:
			k.append(0)
	for q in k:
		print(q, end='')
	print('')


for i in range(int(input())):
	t = input()
	l = ''
	t1 = t[6:8]
	if t1 == 'AM':
		(s1, s2) = (int(t[:2]), int(t[3:5]))
		if s1 == int(12):
			t = s2
		else:
			t = s1 * 60 + s2
	else:
		(s1, s2) = (int(t[:2]), int(t[3:5]))
		if s1 == int(12):
			t = 12 * 60 + s2
		else:
			t = 12 * 60 + s1 * 60 + s2
	for i in range(int(input())):
		s = input()
		sp1 = s[6:8]
		sp2 = s[15:]
		(s3, s4) = (0, 0)
		if sp1 == 'AM':
			(s1, s2) = (int(s[:2]), int(s[3:5]))
			if s1 == int(12):
				s3 = s2
			else:
				s3 = s1 * 60 + s2
		else:
			(s1, s2) = (int(s[:2]), int(s[3:5]))
			if s1 == int(12):
				s3 = 12 * 60 + s2
			else:
				s3 = 12 * 60 + s1 * 60 + s2
		if sp1 == 'AM' and sp2 == 'AM':
			(s1, s2) = (int(s[9:11]), int(s[12:14]))
			if s1 == int(12):
				s4 = s2
			else:
				s4 = s1 * 60 + s2
		elif sp1 == 'AM' and sp2 == 'PM':
			(s1, s2) = (int(s[9:11]), int(s[12:14]))
			if s1 == int(12):
				s4 = s1 * 60 + s2
			else:
				s4 = 12 * 60 + s1 * 60 + s2
		elif sp1 == 'PM' and sp2 == 'PM':
			(s1, s2) = (int(s[9:11]), int(s[12:14]))
			if s1 == int(12):
				s4 = 12 * 60 + s2
			else:
				s4 = 12 * 60 + s1 * 60 + s2
		if s3 <= t <= s4:
			l = l + '1'
		else:
			l = l + '0'
	print(l)


def convert24(str1):
	if str1[-2:] == 'AM' and str1[:2] == '12':
		return '00' + str1[2:-2]
	elif str1[-2:] == 'AM':
		return str1[:-2]
	elif str1[-2:] == 'PM' and str1[:2] == '12':
		return str1[:-2]
	else:
		return str(int(str1[:2]) + 12) + str1[2:8]
for _ in range(int(input())):
	answer = ''
	(parentMeet, duration) = map(str, input().split())
	converted = convert24(parentMeet + ' ' + duration)
	(time, waste) = converted.split(' ')
	(hourStr, minutesStr) = time.split(':')
	finalStr = hourStr + '.' + minutesStr
	final = float(finalStr)
	numFriends = int(input())
	for i in range(numFriends):
		(time1, duration1, time2, duration2) = map(str, input().split())
		startConverted = convert24(time1 + ' ' + duration1)
		(time1, waste1) = startConverted.split(' ')
		(hourStr1, minutesStr1) = time1.split(':')
		finalStr1 = hourStr1 + '.' + minutesStr1
		final1 = float(finalStr1)
		endConverted = convert24(time2 + ' ' + duration2)
		(time2, waste2) = endConverted.split(' ')
		(hourStr2, minutesStr2) = time2.split(':')
		finalStr2 = hourStr2 + '.' + minutesStr2
		final2 = float(finalStr2)
		if final1 <= final and final <= final2:
			answer += '1'
		else:
			answer += '0'
	print(answer)


o = int(input())
for i in range(o):
	P = input()
	N = int(input())
	L = []
	R = []
	lhr = []
	lmn = []
	lap = []
	rhr = []
	rmn = []
	rap = []
	for j in range(N):
		x = input()
		a = slice(0, 8)
		b = slice(9, 17)
		L.append(x[a])
		R.append(x[b])
	for j in range(N):
		st = ''
		st += L[j][0]
		st += L[j][1]
		lhr.append(int(st))
		st = ''
		st += L[j][3]
		st += L[j][4]
		lmn.append(int(st))
		lap.append(L[j][6])
		if lap[j] == 'A':
			if lhr[j] == 12:
				lhr[j] = 0
		elif lhr[j] < 12:
			lhr[j] += 12
		st = ''
		st += R[j][0]
		st += R[j][1]
		rhr.append(int(st))
		st = ''
		st += R[j][3]
		st += R[j][4]
		rmn.append(int(st))
		rap.append(R[j][6])
		if rap[j] == 'A':
			if rhr[j] == 12:
				rhr[j] = 0
		elif rhr[j] < 12:
			rhr[j] += 12
	st = ''
	st += P[0]
	st += P[1]
	phr = int(st)
	st = ''
	st += P[3]
	st += P[4]
	pmn = int(st)
	pap = P[6]
	if pap == 'A':
		if phr == 12:
			phr = 0
	elif phr < 12:
		phr += 12
	ans = []
	for j in range(N):
		if phr == lhr[j]:
			if pmn >= lmn[j]:
				if phr == rhr[j]:
					if pmn <= rmn[j]:
						ans.append('1')
					else:
						ans.append('0')
				elif phr < rhr[j]:
					ans.append('1')
				else:
					ans.append('0')
			else:
				ans.append('0')
		elif phr > lhr[j]:
			if phr == rhr[j]:
				if pmn <= rmn[j]:
					ans.append('1')
				else:
					ans.append('0')
			elif phr < rhr[j]:
				ans.append('1')
			else:
				ans.append('0')
		else:
			ans.append('0')
	res = ''
	res = res.join(ans)
	print(res)


def hr_conversion(time):
	(t, ap) = time.split()
	(h, m) = t.split(':')
	result = ''
	if ap == 'PM' and h != '12':
		result = str(int(h) + 24) + ':' + m
		return result
	elif ap == 'AM' and h == '12':
		return '00' + ':' + m
	else:
		return t
for _ in range(int(input())):
	P = hr_conversion(input())
	n = int(input())
	result = ''
	for _ in range(n):
		(L, l, R, r) = input().split()
		L = hr_conversion(L + ' ' + l)
		R = hr_conversion(R + ' ' + r)
		if P >= L and P <= R:
			result += '1'
		else:
			result += '0'
	print(result)


def convertTime(time):
	time = time.split()
	actTime = list(map(int, time[0].split(':')))
	if 'AM' in time:
		if actTime[0] == 12:
			actTime[0] = 0
		return actTime
	if actTime[0] != 12:
		actTime[0] += 12
	return actTime

def listToTime(arr):
	arr = arr.split()
	return [convertTime(' '.join(arr[:2])), convertTime(' '.join(arr[2:]))]

def canAttend(p, l, r):
	if p[0] == l[0] and p[1] >= l[1]:
		if p[0] == r[0] and p[1] <= r[1] or p[0] < r[0]:
			return '1'
	if p[0] > l[0] and p[0] <= r[0]:
		if p[0] == r[0] and p[1] <= r[1]:
			return '1'
		if p[0] < r[0]:
			return '1'
	return '0'
t = int(input())
for _ in range(t):
	p = convertTime(input())
	out = ''
	for i in range(int(input())):
		(l, r) = listToTime(input())
		out += canAttend(p, l, r)
	print(out)


def format24(p, s):
	if p[:2] == '12' and s == 'AM':
		a = 0
	elif p[:2] != '12' and s == 'PM':
		a = int(p[:2]) + 12
	else:
		a = int(p[:2])
	return a * 60 + int(p[3:])
for _ in range(int(input())):
	p = input().split()
	n = int(input())
	pi = format24(p[0], p[1])
	for i in range(n):
		(l, a, r, s) = input().split()
		(li, ri) = (format24(l, a), format24(r, s))
		if li <= pi and ri >= pi:
			print(1, end='')
		else:
			print(0, end='')
	print()


for T in range(int(input())):
	result = []
	(p1, p2) = map(str, input().split())
	(p1_1, p1_2) = map(str, p1.split(':'))
	if p1_1 == '12' and p2 == 'AM':
		p1_1 = 0
	if p2 == 'PM' and p1_1 != '12':
		p1_1 = int(p1_1)
		p1_1 += 12
	p_m = int(p1_1) * 60 + int(p1_2)
	N = int(input())
	for i in range(0, N):
		(t1, t2, t3, t4) = map(str, input().split())
		(t1_1, t1_2) = map(str, t1.split(':'))
		(t3_1, t3_2) = map(str, t3.split(':'))
		if t1_1 == '12' and t2 == 'AM':
			t1_1 = 0
		if t3_1 == '12' and t4 == 'AM':
			t3_1 = 0
		if t2 == 'PM' and t1_1 != '12':
			t1_1 = int(t1_1)
			t1_1 += int(12)
		if t4 == 'PM' and t3_1 != '12':
			t3_1 = int(t3_1)
			t3_1 += int(12)
		t1_m = int(t1_1) * 60 + int(t1_2)
		t3_m = int(t3_1) * 60 + int(t3_2)
		if t1_m > t3_m:
			t3_m += 24
		if t1_m <= p_m and p_m <= t3_m:
			result.append('1')
		else:
			result.append('0')
	for i in result:
		print(i, end='')
	print('')