My Python Notes

python-notes.txt

#!/bin/python3

import math
import os
import random
import re
import sys


#
# Complete the 'apply_contractions' function below.
#

CONTRACTIONS = {
    ("is", "not"): "isn't",
    ("are", "not"): "aren't",
    ("will", "not"): "won't",
    ("has", "not"): "hasn't",
    ("have", "not"): "haven't",

    ("i", "am"): "i'm",
    ("he", "is"): "he's",
    ("she", "is"): "she's",
    ("they", "are"): "they're",
    ("you", "are"): "you're",

    ("i", "have"): "i've",
    ("he", "has"): "he's",
    ("she", "has"): "she's",
    ("they", "have"): "they've",
    ("you", "have"): "you've",
}

def apply_contractions(sentence: str) -> str:
    tokens=sentence.split(" ")
    for i in range(len(tokens)-1):
        t=(tokens[i],tokens[i+1])
        if (t in CONTRACTIONS.keys() and (random.random() >= 0.5)):
            tokens[i]=CONTRACTIONS[t]
            tokens[i+1]=""
            i+=1
    return ' '.join(tokens).strip().replace("  ", " ")
    


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    try:
        sentence = input()
    except EOFError:
        sentence = ""

    result = apply_contractions(sentence)

    fptr.write(result + '\n')

    fptr.close()

```


# Enter your code here. Read input from STDIN. Print output to STDOUT
students, subjects = map(int,input().split())
score_list = []
for _ in range(int(subjects)):
    scores = list(map(float, input().split()))
    score_list.append(scores)

for i in zip(*score_list):
    print(sum(i)/subjects)



---


x, k = map(int,input().split())
p = input()

print (eval(p)==k)



--- sort array on index k


#!/bin/python3

import math
import os
import random
import re
import sys



if __name__ == '__main__':
    nm = input().split()

    n = int(nm[0])

    m = int(nm[1])

    arr = []

    for _ in range(n):
        arr.append(list(map(int, input().rstrip().split())))

    k = int(input())

    data=list(arr)
    data_sorted=sorted(data, key=lambda data: data[k])
    for data_item in data_sorted:
        print(*data_item)


--- all positive and any palindrome
# Enter your code here. Read input from STDIN. Print output to STDOUT
n = int(input())
numbers = input().split(" ", n)

def positive(x): return int(x)>0
def isPalindrome(x): return x == x[::-1]

print( all(list(map(positive, numbers))) and any(list(map(isPalindrome,numbers))))

--- sort by function on characters
# Enter your code here. Read input from STDIN. Print output to STDOUT
def sorting_function(element):
    if element.isalpha() & element.islower():
        priority = 0
    elif element.isalpha() & element.isupper():
        priority = 1
    elif element.isdigit() & int(element)%2 == 1:
        priority = 2
    else:
        priority = 3
    return priority, element

print(''.join(sorted(list(input()), key=sorting_function)))


--- Group numbers by count

# Enter your code here. Read input from STDIN. Print output to STDOUT
import itertools

numbers=input()
data_grouped=itertools.groupby(numbers)

for k,g in data_grouped:
    print ( (len(list(g)), int(k) ) , end=' ')


---

# Find the probability that at least one of the  indices selected will contain the letter: ''.

import itertools

n=int(input())
chars=input().split(" ", n)
k=int(input())

indices=list(itertools.combinations(chars,k))
matches=len(list(itertools.filterfalse(lambda index: "a" not in index, indices)))
print(matches/len(indices))


---

# find maximum option of equation across all combinations

from itertools import product

k,m=map(int, input().split(" "))

def square(x):
    return x*x

def equation(x):
    return sum(map(square, x)) % m

lines=[]
for _ in range(k):
    n = list(map(int, input().split(" ")))
    lines.append(list(n[1:]))

all_candidates=product(*lines)
print(max(map(equation, all_candidates)))


---

# HTML parsing

from html.parser import HTMLParser

class MyHTMLParser(HTMLParser):
    def handle_starttag(self, tag, attrs):
        print(f"Start : {tag}")
        for name,value in attrs:
            print(f"-> {name} > {value}")

    def handle_startendtag(self, tag, attrs):
        print(f"Empty : {tag}")
        for name,value in attrs:
            print(f"-> {name} > {value}")

    def handle_endtag(self, tag):
        print(f"End   : {tag}")


parser = MyHTMLParser()
for _ in range(int(input())):
    parser.feed(input())
parser.close()


---

# HTML processing

from html.parser import HTMLParser

class MyHTMLParser(HTMLParser):
    def handle_comment(self, data):
        lines=len(data.splitlines())
        if (lines == 1):
            print(">>> Single-line Comment")
            print(data)
        elif (lines > 1):
            print(">>> Multi-line Comment")
            print(data)

    def handle_data(self, data):
        if (str(data.rstrip()) != ""):
            print(">>> Data")
            print(data)


html = ""       
for i in range(int(input())):
    html += input().rstrip()
    html += '\n'
    
parser = MyHTMLParser()
parser.feed(html)
parser.close()

---

import re
from collections import Counter

t=int(input())

for _ in range(t):
    uid=input()
    if (re.match('[a-zA-Z0-9]{10}', uid) != None) and \
        (re.match('.*[A-Z].*[A-Z].*', uid) != None) and \
        (re.match('.*[0-9].*[0-9].*[0-9].*', uid) != None):
        if (len(Counter(list(uid))) == 10):
            print("Valid")
        else:
            print("Invalid")
    else:
        print("Invalid")


--- example of regex look ahead / look behind - find all 2-or-more consecutive vowels between consonants

import re

m=re.findall(r'(?<=[qwrtypsdfghjklzxcvbnmQWRTYPSDFGHJKLZXCVBNM])([aeiouAEIOU]{2,})(?=[qwrtypsdfghjklzxcvbnmQWRTYPSDFGHJKLZXCVBNM])',input())
if m:
    for i in m:
        print(i)
else:
    print(-1)    

 

--- example of regex - iterate search on string

import re

s=input()
k=input()

if (k not in s):
    print("(-1, -1)")
else:
    start_index=0
    while (len(s) > 0):
        m = re.search(f"({k})", s)
        if m:
            not_found=None
            print("(" + str(m.start()+start_index) + ", " + str(m.end()+start_index-1) + ")")
            start_index=start_index+m.start()+1
            s=s[m.start()+1:]
        else:
            break

--- CC validation

import re

n=int(input())
for _ in range(n):
    cc=input()
    valid=(re.fullmatch(r"^[456]\d{3}(-?\d{4}){3}$", cc) != None and \
         re.search(r"([0-9])(-?\1){3}", cc) == None)
    print((("Invalid", "Valid")[valid]))

--- zip codes

regex_integer_in_range = r"^[1-9]\d{5}$"
regex_alternating_repetitive_digit_pair = r"(\d)(?=\d\1)"    # Do not delete 'r'.



--- Iterate over functions

import numpy

numpy.set_printoptions(legacy='1.13')

a=input().split()
na=numpy.array(a, float)

functions=[numpy.floor, numpy.ceil, numpy.rint]
[ print(f(na)) for f in functions ]

# for f in functions: print(functions(na))
# print(map(lambda f: f(na), functions))


--- numpy sum and numpy prod

import numpy

n,m=map(int, input().split())

arrays=[]
for _ in range(n):
    arrays.append(numpy.array(input().split(),int))

print(numpy.prod(numpy.sum(arrays, axis = 0)))



--- print students with second latest grade

if __name__ == '__main__':
    records = []
    for _ in range(int(input())):
        name = input()
        score = float(input())
        records.append([name, score])

    scores=list(set(map(lambda record: record[1], records)))
    target_score=sorted(scores)[1]
    students=filter(lambda record: record[1]==target_score, records)
    for student in sorted(students):
        print(student[0])

--- pypy3 vs python3

if __name__ == '__main__':
    n = int(input())
    integer_list = map(int, input().split())
    t=tuple(integer_list)
    print(hash(t))


I like the elegance of the one-liners in the discussion, but I cannot get past the extra memory usage in a practical application:

```
def count_substring(string, sub_string):
    count,sl = 0, len(sub_string)
    for i in range(len(string)-sl+1):
        if sub_string == string[i:i+sl]:
            count+=1
    return count

```

--- Evaluate a list of functions up to the first match within string

from itertools import filterfalse

if __name__ == '__main__':
    s = input()
    functions=[str.isalnum, str.isalpha, str.isdigit, str.islower, str.isupper]
    for fn in functions:
        chars_matching_function=len(s)-len(list(filterfalse(fn, s)))
        print(chars_matching_function > 0)

--- swapcase possibilities


def swap_char(c):
    return c.lower() if c.isupper() else c.upper()

def swap_case(s):
    # return ''.join([i.lower() if i.isupper() else i.upper() for i in s])
    # return s.swapcase
    return ''.join(map(swap_char, s))

if __name__ == '__main__':


--- floormat

s=list(map(int, input().split()))
n,m=s[0],s[1]

for i in range(n):
    if (i == n//2):
        middle="WELCOME"
    else:
        middle_repeats=i*2+1 if i < n//2 else (n-i)*2-1
        middle='.|.'*(middle_repeats)
    print(middle.center(m, '-'))


--- print formatted numbers

def print_formatted(number):
    width=len("{0:b}".format(number))
    for i in range(number):
        print("{0:{width}} {0:>{width}o} {0:>{width}X} {0:>{width}b}".format(i+1, width=width))


--- rangoli ---

def print_rangoli(size):
    left=""
    middle_char_ord=ord('a')+size-1
    middle=chr(middle_char_ord)
    for i in range(1,size*2):
        middle_string=left+chr(middle_char_ord)+left[::-1]
        print(middle_string.center(size*4-3, '-'))
        if i < size:
            left=left+chr(middle_char_ord)+"-"
            middle_char_ord -= 1
        else:
            left=left[:-2]
            middle_char_ord += 1

--- capitalize ---

#!/bin/python3

import math
import os
import random
import re
import sys

def solve(s):
    return ' '.join([i.capitalize() for i in s.split(' ')
    # result=""
    # for i in range(0,len(s)):
    #     if (i==0 or s[i-1]==' '):
    #         result+=s[i].upper()
    #     else:
    #         result+=s[i]
    # return result
            

--- number triangle

for i in range(1,int(input())):
    print (i*pow(10,i-1) + sum(map(lambda x: x*pow(10,i*2-x-1) + x*pow(10,x-1), range(1,i))))

---

for i in range(1,int(input())):
    print (sum(map(lambda x: i*pow(10,x), range(0,i))))




---- Counter example

from collections import Counter

x=int(input())
shoe_sizes=Counter(map(int, input().split()))
n=int(input())

total=0
for _ in range(n):
    size, value = tuple(map(int,input().split()))
    if shoe_sizes[size] > 0:
        shoe_sizes.subtract({size})
        total+=value

print(total)


--- default dict example

from collections import defaultdict

n,m=tuple(map(int,input().split()))

a=defaultdict(list)
[ a[input()].append(str(i)) for i in range(1,n+1) ]

for _ in range(m):
    bi=input()
    if bi in a.keys():
        print(*a[bi])
    else:
        print(-1)

--- permutations

from itertools import permutations

s,ks=tuple(input().split())
k=int(ks)

[ print(*[''.join(pi)]) for pi in sorted(permutations(s,k)) ]


--- combinations

from itertools import combinations

s,k=tuple(input().split())
ss=sorted(s)

for ki in range(int(k)):
    [ print(''.join(ci)) for ci in combinations(ss,ki+1) ]

---

def average(array):
    dh=set(array)
    return f"{round(sum(dh)/len(dh),3)}"

if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split()))
    result = average(arr)
    print(result)

--- calendar

import calendar

mm,dd,yyyy=tuple(map(int,input().split()))
print(calendar.day_name[calendar.weekday(yyyy, mm, dd)].upper())


--- format time

# https://docs.python.org/3.9/library/datetime.html?highlight=strptime#strftime-and-strptime-behavior
def time_delta(t1, t2):
    fmt="%a %d %b %Y %H:%M:%S %z"
    t1s=datetime.datetime.strptime(t1, fmt).timestamp()
    t2s=datetime.datetime.strptime(t2, fmt).timestamp()
    return str(abs(int(t1s-t2s)))

--- Try-except

import re

t=int(input())

for _ in range(t):
    try:
        re.compile(input())
        print(True)
    except:
        print(False)


--- numpy

import numpy

n=int(input())

a=[ list(map(float, input().split())) for _ in range(n) ]
print (round(numpy.linalg.det(a),2))

--- Regex + lambda

import re

n=int(input())

pattern=re.compile("(?<= )&&(?= )|(?<= )\|\|(?= )")
l=lambda m: "and" if m.group(0) == "&&" else "or"

for _ in range(n):
    print(pattern.sub(l, input()))


--- Roman numerals - regexp

r"(M{0,3})(C[DM]|D?C{0,3})(X[LC]|L?X{0,3})(I[VX]|V?I{0,3})$"

--- email parsing

import email.utils
import re

pattern=re.compile(r"^([a-zA-Z])([a-zA-Z0-9._\-)*\@([a-zA-Z])+\.([a-zA-Z]){1,3}$")
n=int(input())
for _ in range(n):
    email_str=input()
    email_parse=email.utils.parseaddr(email_str)
    if re.match(pattern, email_parse[1]) != None:
        print(email_str)
    # else:
    #     print("R", email_parse, email_parse[1])


---

Validate number

import re

pattern=re.compile(r"^[+\-]?[0-9]*\.[0-9]+$")
n=int(input())
for _ in range(n):
    number=input()
    print (bool(re.match(pattern, number)))


--- Named tuples

from collections import namedtuple
n,Record=int(input()), namedtuple('Record', ','.join(input().split()))
records=[ Record(*(input().split())) for _ in range(n) ]
print(round(sum(map(int, lambda r: int(r.MARKS), records))/n, 2))


--- Ordered dict

from collections import OrderedDict

prices = OrderedDict()

n=int(input())
for _ in range(n):
    l=input()
    price_str_index=l.rfind(" ")
    name=l[0:price_str_index]
    price=int(l[price_str_index+1:])
    current_net_price = prices[name] if name in prices.keys() else 0
    prices[name] = current_net_price + price

for n,p in prices.items():
    print(n, p)


---


n = int(input())
dic = {}

for i in range(n):
    a = input().split()
    item = " ".join(a[:-1])
    price = int(a[-1])

    dic[item] = price + dic.get(item, 0)

for i, j in dic.items():
    print(i, j)


--- numpy zeros and ones

import numpy

n=tuple(map(int,input().split()))

print (numpy.zeros(n, dtype = int))
print (numpy.ones(n, dtype = int))


--- numpy eye matrix

import numpy
numpy.set_printoptions(legacy='1.13')

n,m=tuple(map(int,input().split()))

print (numpy.eye(n, m, k = 0))


--- numpy function array

import numpy

n,m=tuple(map(int,input().split()))

a=[list(map(int, input().split())) for _ in range(n) ]
b=[list(map(int, input().split())) for _ in range(n) ]

functions = [ numpy.add, numpy.subtract, numpy.multiply, numpy.floor_divide, numpy.mod, numpy.power ]
[ print(f(a,b)) for f in functions ]

--- Complex - object oriented

import math

class Complex(object):
    real=0.0
    imaginary=0.0    
    
    def __init__(self, real, imaginary):
        self.real=real
        self.imaginary=imaginary
        
    def __add__(self, no):
        return Complex(self.real + no.real, self.imaginary + no.imaginary)
        
    def __sub__(self, no):
        return Complex(self.real - no.real, self.imaginary - no.imaginary)
        
    def __mul__(self, no):
        return Complex(self.real * no.real - self.imaginary * no.imaginary, self.real * no.imaginary + self.imaginary * no.real)

    def __truediv__(self, no):
        denominator= no.real**2 + no.imaginary**2
        return Complex((self.real * no.real + self.imaginary * no.imaginary)/denominator, \
                       (self.imaginary * no.real - self.real * no.imaginary)/denominator)

    def mod(self):
        return "%.2f+0.00i" % math.sqrt(self.real**2 + self.imaginary**2)

    def __str__(self):
        if self.imaginary == 0:
            result = "%.2f+0.00i" % (self.real)
        elif self.real == 0:
            if self.imaginary >= 0:
                result = "0.00+%.2fi" % (self.imaginary)
            else:
                result = "0.00-%.2fi" % (abs(self.imaginary))
        elif self.imaginary > 0:
            result = "%.2f+%.2fi" % (self.real, self.imaginary)
        else:
            result = "%.2f-%.2fi" % (self.real, abs(self.imaginary))
        return result

if __name__ == '__main__':
    c = map(float, input().split())
    d = map(float, input().split())
    x = Complex(*c)
    y = Complex(*d)
    print(*map(str, [x+y, x-y, x*y, x/y, x.mod(), y.mod()]), sep='\n')


--- dequeue


from collections import deque

n=int(input())

d=deque()
for _ in range(n):
    cmd=input()
    if cmd.startswith("popleft"):
        d.popleft()
    elif cmd.startswith("pop"):
        d.pop()
    elif cmd.startswith("appendleft"):
        x=cmd.split()[1]
        d.appendleft(x)
    elif cmd.startswith("append"):
        x=cmd.split()[1]
        d.append(x)
    else:
        print("Unknown method: " + cmd)

print(*d)

---

from collections import deque
d  = deque()
for _ in range(int(input())):
     o , *l = input().split()
     eval(f"d.{o}(*l)")
print(*d)


---

from collections import deque

t = int(input())

for _ in range(t):
    n = int(input())
    pile=deque(map(int, input().split()))

    stackable=1
    pile_top=2**31
    while len(pile) > 0:
        # print(pile_top, pile)
        blocks = [ pile.popleft() ]
        sorted_blocks = blocks
        if len(pile) > 0:
            blocks.append(pile.pop())
            sorted_blocks = sorted(blocks)
            
        if sorted_blocks[-1] <= pile_top:
            pile_top = sorted_blocks[0]
        else:
            stackable=0
            break

    print("Yes") if stackable == 1 else print("No")

--- set mutations

_,a = int(input()), set(map(int, input().split()))
n=int(input())

for _ in range(n):
    o=input().split()[0]
    b = set(map(int, input().split()))
    eval(f"a.{o}(b)")
print(sum(a))


--- issuperset

a=set(input().split())
n=int(input())
result=True
for _ in range(n):
    b=set(input().split())
    if not a.issuperset(b):
        result=False
        break
print(result)

--- email filter

import re

pattern=re.compile(r"^([a-zA-Z0-9_-])+@([a-zA-Z0-9])+\.([a-zA-Z]){1,3}$")

def fun(s):
    return re.match(pattern, s) != None

def filter_mail(emails):
    return list(filter(fun, emails))

if __name__ == '__main__':
    n = int(input())
    emails = []
    for _ in range(n):
        emails.append(input())

filtered_emails = filter_mail(emails)
filtered_emails.sort()
print(filtered_emails)


--- numpy reverse array

import numpy

def arrays(arr):
    return numpy.array(arr[::-1], float)

arr = input().strip().split(' ')


--- numpy reshape

import numpy

a=numpy.array(input().split(), int)
print (numpy.reshape(a, (3,3)))


--- numpy concatenate

import numpy

n,m,p=list(map(int, input().split()))

a1=[ numpy.array(input().split(), int) for _ in range(n) ]
a2=[ numpy.array(input().split(), int) for _ in range(m) ]

print (numpy.concatenate((a1,a2)))


--- xml sum of attrib

import sys
import xml.etree.ElementTree as etree

def get_attr_number(node):
    sum=len(node.attrib)
    for n in node:
        sum += get_attr_number(n)
    return sum

if __name__ == '__main__':
    sys.stdin.readline()
    xml = sys.stdin.read()
    tree = etree.ElementTree(etree.fromstring(xml))
    root = tree.getroot()
    print(get_attr_number(root))


--- name directory

import operator

def person_lister(f):
    def inner(people):
        return ([f(person) for person in sorted(people, key=lambda p: int(p[2])) ])
    return inner

@person_lister
def name_format(person):
    return ("Mr. " if person[3] == "M" else "Ms. ") + person[0] + " " + person[1]

if __name__ == '__main__':
    people = [input().split() for i in range(int(input()))]
    print(*name_format(people), sep='\n')

--- format phone number

def wrapper(f):
    def fun(l):
        return f(["+91 {} {}".format(n[-10:-5], n[-5:]) for n in l ])
    return fun

@wrapper


--- +/- function

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'plusMinus' function below.
#
# The function accepts INTEGER_ARRAY arr as parameter.
#

def plusMinus(arr):
    pos,neg=0,0
    for i in arr:
        if i > 0: pos+=1 
        if i < 0: neg+=1 
    l=len(arr)
    zero=l-pos-neg
    print("{:.6f}".format(pos/l))
    print("{:.6f}".format(neg/l))
    print("{:.6f}".format(zero/l))

if __name__ == '__main__':
    n = int(input().strip())

    arr = list(map(int, input().rstrip().split()))

    plusMinus(arr)

--- python datetime

import datetime

def timeConversion(s):
   t=datetime.datetime.strptime(s, "%I:%M:%S%p")
   return datetime.datetime.strftime(t, "%H:%M:%S")

--- fruit counter

def countApplesAndOranges(s, t, a, b, apples, oranges):
    ac,oc=0,0
    # for f in apples: ac += (1 if (s <= (a + f) <= t) else 0)
    # for f in oranges: oc += (1 if (s <= (b + f) <= t) else 0)
    print (reduce(lambda c, f: c + (1 if (s <= (a + f) <= t) else 0), apples, 0))
    print (reduce(lambda c, f: c + (1 if (s <= (b + f) <= t) else 0), oranges, 0))
    # print (ac)
    # print (oc)


--- step counter

def kangaroo(x1, v1, x2, v2):
    i=0
    nd=-1
    d=abs(x1 - x2)
    while (nd != 0) and (nd < d):
        i = i+1
        nd=abs(x1 + v1*i - x2 - v2*i)
    return "YES" if nd == 0 else "NO"

--- graph theory

#!/bin/python3

import math
import os
import random
import re
import sys
from collections import OrderedDict

def map_cell(maze, coords):
    return "#" \
        if coords[0] < 1 or coords[0] > len(maze) or \
            coords[1] < 1 or coords[1] > len(maze[0]) \
        else maze[coords[0]-1][coords[1]-1]

def blocked_path(cell):
    return cell == '#'

def blocked_left(maze, coords):
    return blocked_path(map_cell(maze, (coords[0], coords[1]-1)))

def blocked_right(maze, coords):
    return blocked_path(map_cell(maze, (coords[0], coords[1]+1)))

def blocked_top(maze, coords):
    return blocked_path(map_cell(maze, (coords[0]-1, coords[1])))

def blocked_bottom(maze, coords):
    return blocked_path(map_cell(maze,  (coords[0]+1, coords[1])))

def dead_end(maze, coords):
    return blocked_left(maze, coords) and \
           blocked_right(maze, coords) and \
           blocked_top(maze, coords) and \
           blocked_bottom(maze, coords)
      
def move_alex(maze, tunnels, new_alex):
    if new_alex in tunnels:
        new_alex=tunnels[new_alex]
    return new_alex

def build_graph(graph, maze, tunnels, visited, alex):

    if alex not in graph.keys():
        graph[alex]=[]

    if dead_end(maze, alex):
        graph[alex].append(("X","X"))
        return ("X","X")

    alex_cell_type=map_cell(maze, alex)
    if alex_cell_type in "*#%":
        graph[alex].append((alex_cell_type, alex_cell_type))
        return (alex_cell_type, alex_cell_type)

    if (not blocked_left(maze, alex)):
        new_alex=(alex[0], alex[1]-1)
        if new_alex not in visited or map_cell(maze, new_alex) in "*#%" or dead_end(maze, new_alex):
            visited.add(new_alex)
            new_alex=move_alex(maze, tunnels, new_alex)
            new_cell = build_graph(graph, maze, tunnels, visited, new_alex)
            graph[alex].append(new_alex)
    if (not blocked_right(maze, alex)):
        new_alex=(alex[0], alex[1]+1)
        if new_alex not in visited or map_cell(maze, new_alex) in "*#%" or dead_end(maze, new_alex):
            visited.add(new_alex)
            new_alex=move_alex(maze, tunnels, new_alex)
            new_cell = build_graph(graph, maze, tunnels, visited, new_alex)
            graph[alex].append(new_alex)
    if (not blocked_top(maze, alex)):
        new_alex=(alex[0]-1, alex[1])
        if new_alex not in visited or map_cell(maze, new_alex) in "*#%" or dead_end(maze, new_alex):
            visited.add(new_alex)
            new_alex=move_alex(maze, tunnels, new_alex)
            new_cell = build_graph(graph, maze, tunnels, visited, new_alex)
            graph[alex].append(new_alex)
    if (not blocked_bottom(maze, alex)):
        new_alex=(alex[0]+1, alex[1])
        if new_alex not in visited or map_cell(maze, new_alex) in "*#%" or dead_end(maze, new_alex):
            visited.add(new_alex)
            new_alex=move_alex(maze, tunnels, new_alex)
            new_cell = build_graph(graph, maze, tunnels, visited, new_alex)
            graph[alex].append(new_alex)
            
    return alex
    # print("Newly visited", visited)

if __name__ == '__main__':
    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])
    m = int(first_multiple_input[1])
    k = int(first_multiple_input[2])

    alex=(0,0)
    maze=[]
    for n_itr in range(n):
        row = input()
        maze.append(row)
        find_alex=row.find("A")
        if  find_alex>= 0:
            alex=(n_itr+1, find_alex+1)

    tunnels={}
    for k_itr in range(k):
        second_multiple_input = input().rstrip().split()

        i1 = int(second_multiple_input[0])
        j1 = int(second_multiple_input[1])

        i2 = int(second_multiple_input[2])
        j2 = int(second_multiple_input[3])

        tunnels[(i1,j1)]=(i2,j2)
        tunnels[(i2,j2)]=(i1,j1)

    # print(tunnels)
    # print(f"Alex at: {alex}")
    # print(f"Bombs: {bombs}")
    # print(f"Dead ends: {dead_ends}")
    
    visited=set()
    graph=OrderedDict()
    build_graph(graph, maze, tunnels, visited, alex)

    exited=0
    bombed=0
    dead_ended=0
    visits=0
    # print(len(visited))
    # for k in graph:
    #     print(k, graph[k])

    for path in graph.values():
        exited +=  path.count(('%','%'))
        dead_ended += path.count(('X','X'))
        bombed += path.count(('*','*'))
    # print(dead_ended, bombed, exited)
    print(0 if exited == 0 else exited/(exited+bombed+dead_ended))


--- Day of programmer
--- https://www.hackerrank.com/challenges/day-of-the-programmer/problem?isFullScreen=true

def dayOfProgrammer(year):
    if year < 1918:
        if year % 4 == 0:
            dop=datetime.date(year=year,month=9,day=12)
        else:
            dop=datetime.date(year=year,month=9,day=13)
    else:
        d=datetime.date(year=year,month=1,day=1)
        if year == 1918:
            dop=d.fromordinal(d.toordinal()+268)
        else:
            dop=d.fromordinal(d.toordinal()+255)


--- Page count
--- https://www.hackerrank.com/challenges/drawing-book/problem?isFullScreen=true&h_r=next-challenge&h_v=zen


--- Python jump cloud

```
def jumpingOnClouds(c, k):
    e,i = 100,0
    while True:
        i = (i + k) % n
        e -= 1 + c[i]* 2
        if i == 0: break   # jumped back to origin cloud
    return e
```

Credit to https://www.hackerrank.com/challenges/jumping-on-the-clouds-revisited/forum/comments/1191449 for the idea of `c[i]*2`

--- Append and delete

def appendAndDelete(s, t, k):
    common_chars = 0
    for i in range(min(len(s), len(t))):
        if s[i] == t[i]:
            common_chars = i+1
        else:
            break
    c_to_be_replaced = len(s) + len(t) - common_chars*2
    budget = k - c_to_be_replaced
    return "Yes" if (k >= len(s) + len(t)) or (budget >= 0 and budget % 2 == 0) else "No"

---

Sherlock and Squares

def squares(a, b):
    # counter = reduce(lambda y,x: y + 1 if a <= x**2 <= b else 0, range(int(math.sqrt(a)),int(math.sqrt(b)+1)), 0)
    counter=0
    for i in range(int(math.sqrt(a)),int(math.sqrt(b)+1)):
        if a <= i**2 <=b:
            counter += 1
    return counter

--- no divisible set

def nonDivisibleSubset(k, s):
    result=0
    ki = len(s)
    while ki > 0 and result == 0:
        for i in combinations(s,ki):
            divisible=False
            for j in combinations(i, 2):
                if sum(j) % k == 0:
                    divisible=True
                    break
            if not divisible:
                result=ki
                break
        ki -= 1
    return result


def nonDivisibleSubset(k, s):
    result=0
    ki = len(s)+1
    
    # divisions = []
    # for j in combinations(s, 2):
    #     if sum(j) % k == 0:
    #         divisions.append(j[0])
    #         divisions.append(j[1])
    # c = Counter(divisions)
    # for i,freq in c.most_common():
    #     print(i, freq)
    #     if freq == len(s) -1:
    #         print(s)
    #         s.remove(i)
    # return len(s)

    while ki > 1 and result == 0:
        ki -= 1
        for i in combinations(s,ki):
            divisible=False
            print("Trying", i, ki)
            for j in combinations(i, 2):
                # print(j)
                if sum(j) % k == 0:
                    print("Bombed", j, sum(j), sum(j) % k)
                    divisible=True
                    break
            if not divisible:
                # print("Found", i)
                return ki
    return result

def nonDivisibleSubset(k, s):
    divisible=set()
    indivisible=set()
    ki = len(s)
    for i in permutations(s,2):
        print(i, sum(i), sum(i) % 87)
        if sum(i) % k != 0:
            indivisible.add(i[0])
            indivisible.add(i[1])
        else:
            divisible.add(i[0])
            divisible.add(i[1])
    print(len(divisible))
    print(len(indivisible))
    return len(indivisible)


--- Queen travel

def queensAttack(n, k, r_q, c_q, obstacles):
    # diagonal offsets
    lo_ld = min(r_q, c_q)
    hi_ld = min(n - r_q + 1, n - c_q + 1)
    lo_ud = min(n - r_q + 1, c_q)
    hi_ud = min(r_q, n - c_q + 1)
    offsets = { "ld": [[r_q - lo_ld, c_q - lo_ld], [ r_q + hi_ld, c_q + hi_ld]],
                "lc": [[0, c_q], [n+1, c_q]],
                "ud": [[r_q + lo_ud, c_q - lo_ud], [ r_q - hi_ud, c_q + hi_ud]],
                "rl": [[r_q,0], [r_q,n+1]] }
    # print ("ld", offsets["ld"])
    # print ("ud", offsets["ud"])
    # print ("rl", offsets["rl"])
    # print ("lc", offsets["lc"])
    for o in obstacles:
        rd = o[0]-r_q
        cd = o[1]-c_q
        if rd == cd:
            if rd > 0 and o[0] < offsets["ld"][1][0]:
                offsets["ld"][1] = o
            elif rd < 0 and o[0] > offsets["ld"][0][0]:
                offsets["ld"][0] = o        
        elif rd == -cd:
            if rd > 0 and o[0] < offsets["ud"][0][0]:
                offsets["ud"][0] = o
            elif rd < 0 and o[0] > offsets["ud"][1][0]:
                offsets["ud"][1] = o        
        elif rd == 0:
            if cd < 0 and o[1] > offsets["rl"][0][1]:
                offsets["rl"][0] = o
            elif cd > 0 and o[1] < offsets["rl"][1][1]:
                offsets["rl"][1] = o        
        elif cd == 0:
            if rd > 0 and o[0] < offsets["lc"][1][0]:
                offsets["lc"][1] = o
            elif rd < 0 and o[0] > offsets["lc"][0][0]:
                offsets["lc"][0] = o        
    # print ("ld", offsets["ld"])
    # print ("ud", offsets["ud"])
    # print ("rl", offsets["rl"])
    # print ("lc", offsets["lc"])
    result = offsets["ld"][1][0] - offsets["ld"][0][0] - 2 + \
             offsets["ud"][1][1] - offsets["ud"][0][1] - 2 + \
             offsets["rl"][1][1] - offsets["rl"][0][1] - 2 + \
             offsets["lc"][1][0] - offsets["lc"][0][0] - 2
    return result

--- ACM Teams topics

from itertools import combinations

def acmTeam(topics):
    max_subjects = 0
    max_teams = 0
    for c in combinations(topics,2):
        subjects_bin = bin(int(c[0],2) | int(c[1], 2))
        subjects = subjects_bin.count('1')
        if (subjects == max_subjects):
            max_teams += 1
        elif (subjects > max_subjects):
            max_subjects = subjects
            max_teams = 1
    return [ max_subjects, max_teams]


--- Encrypt ----

def encryption(s):
    ss = s.replace(' ','')
    sss = math.sqrt(len(ss))
    r = math.floor(sss)
    c = math.ceil(sss)
    if (r * c) < len(ss):
        r += 1
    encoded = []
    for ci in range(c):
        cs = ''
        for ri in range(r):
            cs += '' if ri*c+ci >= len(ss) else ss[ri*c+ci]
        encoded.append(cs)
    return(' '.join(encoded))


--- Beautiful triplets ---

def beautifulTriplets(d, arr):
    indices = [ i for i in range(len(arr))]
    result = 0
    for a in combinations(indices,3):
        if (arr[a[1]] - arr[a[0]] == d) and (arr[a[2]] - arr[a[1]] == d):
            result += 1
    return result


def beautifulTriplets(d, arr):
    result = 0
    for i in range(len(arr)-2):
        try:
            j = arr.index(arr[i]+d, i+1)
            k = arr.index(arr[j]+d, j+1)
            result += 1
        except ValueError:
            pass
    return result

--- bigger is greater

def biggerIsGreater(w):
    for i in range(len(w)-2, -1, -1):
        pivot_char = w[i]
        
        # if none of the remaining chars are higher than the 
        # current char, there is no candidate to form a 
        # "higher" word.
        if pivot_char > max(w[i+1:]):
            continue

        # Now look for the lowest character higher than the
        # pivot character and use it in place of the 
        # pivot char.
        right_word = sorted(w[i+1:])
        for j in range(len(right_word)):
            if right_word[j] > pivot_char:
                # Now generate the "smallest" possible word 
                # with the combination of remaining chars and 
                # the old pivot char.
                new_pivot_char = right_word[j]
                new_right_word = [new_pivot_char] + right_word[0:j] + [pivot_char]
                if j+1 < len(right_word):
                     new_right_word += right_word[j+1:]

                left_word = w[:i]
                return ''.join(left_word) + ''.join(new_right_word)

    return "no answer"


--- discounted ---

def howManyGames(p, d, m, s):
    units = 0
    while s >= p:        
        if p <= m:
            units += s // m
            break;
        units += 1
        s -= p
        p -= d

    return units

16 2 1 9981
9917

100 1 1 99
0

    # if p > s:
    #     return 0

    # me = m + p % d
    # ndu = int ((s/p + s/me) / d) + 1
    # ndc = int ( (p + (p - (ndu - 1) * d)) / 2) * ndu
    # du = max(0, (s - ndc) // m)
    # print ("ndu", ndu)
    # print (ndc)
    # print (du, du + ndu)

    # return du + ndu


--- workbook ---

def workbook(n, k, arr):
    special = 0
    page = 0
    for a in arr:
        a1 = page + 1
        if a >= a1:
            for p in range(1,a+1):
                problem_page = (p-1) // k + a1
                if p == problem_page:
                    special += 1
        page += math.ceil(a / k)
    return special

--- strange code ---

# https://www.hackerrank.com/challenges/strange-code/problem?isFullScreen=true

def strangeCounter(t):
    # cycle : t1 to t2                   value 1
    # 0     : 1 to 3                      3 = 3 * 2^0
    # 1     : 4 to 9                      6 = 3 * 2^1
    # 2     : 10 to 21                   12 = 3 * 2^2
    # 3     : 22 to 45                   24 = 3 * 2^3
    # ...
    # n     : 3*2^^n -2 to 3*2^^n-2 + 3*2^n-1  3 * 2^n
    # n     : 3*2^^n -2 to 3*2^^*(n+1)-3       3 * 2^n
    # n     : 3*2^^n -2 to 6*2^^*n -3          3 * 2^n
    #
    # n     : time + value = t1 in next cycle = 3*2^^(n+1) -2
    n = math.floor(math.log((t+2)/3,2))
    v = 3*2**(n+1)-2 - t
    return v 

--- absolute permutation ---
# https://www.hackerrank.com/challenges/absolute-permutation/problem

def absolutePermutation(n, k):
    result = []
    used = set()
    while len(result) < n:
        i = len(result) + 1
        posi = i - k
        if posi > 0 and posi not in used:
            result.append(posi)
        else:
            posi = i + k
            if posi <= n and posi not in used:
                result.append(posi)
            else:
                return [-1]
        used.add(posi)

    return result


--- bomber man ---

https://www.hackerrank.com/challenges/bomber-man/problem?
def bomberMan(n, grid):
    new_grid = []
    for s in range(min(15,n+1)):
        for i in range(len(grid)):
            if s == 0: new_grid.append([])
            for j in range(len(grid[0])):
                if s == 0:
                    if grid[i][j] == ".":
                        new_grid[i].append(0)
                    else:
                        new_grid[i].append(1)
                elif s == 1:
                    if new_grid[i][j] > 0:
                        new_grid[i][j] += 1
                elif s > 1 and s % 2 == 0:
                    new_grid[i][j] += 1
                elif s > 2 and s % 2 == 1:
                    if new_grid[i][j] % 10 == 3:
                        new_grid[i][j] = 0
                        if i > 0: new_grid[i-1][j] = 0
                        if i+1 < len(grid): new_grid[i+1][j] += 10
                        if j > 0: new_grid[i][j-1] = 0
                        if j+1 < len(grid[0]): new_grid[i][j+1] += 10
                    elif new_grid[i][j] >= 10:
                        new_grid[i][j] = 0
                    else:
                        new_grid[i][j] += 1
        if s > 4:
            # All bombs
            if s % 2 == 0 and n % 2 == 0:
                break
            # Mix 1
            if (s - 1) % 4 == 0 and (n - 1) % 4 == 0:
                break
            # Mix 2
            if (s - 3) % 4 == 0 and (n - 3) % 4 == 0:
                break

        print(s)
        for i in range(len(new_grid)):
            print("-".join(map(str, new_grid[i])))

    result = []
    for i in range(len(new_grid)):
        result.append("")
        for j in range(len(new_grid[0])):
            result[i] += "." if new_grid[i][j] == 0 else "O"

    return result

--- two-pluses ---

# https://www.hackerrank.com/challenges/two-pluses


def twoPluses(grid):
    plusses=[]
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] != 'B':
                max_plus_length=min((len(grid)-1)//2, (len(grid[0])-1)//2, i, j, len(grid)-i-1, len(grid[0])-j-1)
                plus = set()
                plus.add((i,j))
                plusses.append(plus)
                for k in range(1, max_plus_length+1):
                    if grid[i-k][j] == 'G' and \
                       grid[i+k][j] == 'G' and \
                       grid[i][j-k] == 'G' and \
                       grid[i][j+k] == 'G':
                        plus.add((i-k,j))
                        plus.add((i+k,j))
                        plus.add((i,j-k))
                        plus.add((i,j+k))
                    else:
                        break
                    subplus = plus.copy()
                    plusses.append(subplus)

    max_area_product = 0
    for pi in plusses:
        for pj in plusses:
            if not pi.intersection(pj):
                max_area_product = max(max_area_product, len(pi)*len(pj))
            
    return max_area_product

--- Larry's array ---

# https://www.hackerrank.com/challenges/larrys-array
def larrysArray(A):
    v=1
    while v < len(A):
        if A[v-1] == v:
            v += 1
        else:
            i = v-1
            iv = A.index(v, i, len(A))
            rotation_start = max(i, iv-2)
            if rotation_start >= len(A)-2:
                return "NO"
            a,b,c = A[rotation_start],A[rotation_start+1],A[rotation_start+2]
            A[rotation_start], A[rotation_start+1],A[rotation_start+2] = b,c,a
    
    return "YES"

--- 

# https://www.hackerrank.com/challenges/reduced-string/problem?isFullScreen=true

def superReducedString(s):
    result = reduce(lambda x,y: x+y if len(x) == 0 or x[-1] != y else x[:-1] , s)
            
    return result if len(result) > 0 else "Empty String"


def reduce_string(reduced_string, next_char):
    if len(reduced_string) > 0 and reduced_string[-1] == next_char:
        reduced_string[:-1]
    else:
        reduced_string + next_char

def superReducedString(s):
    result = reduce(reduce_string , s)
    return result if len(result) > 0 else "Empty String"

---

# https://www.hackerrank.com/challenges/insertionsort2/problem

def insertionSort2(n, arr):
    for i in range(n):
        for j in range(i):
            if arr[j] > arr[i]:
                ai = arr[i]
                for k in range(i, j, -1):
                    # print(k)
                    arr[k] = arr[k-1]
                arr[j] = ai
        if i > 0:
            print(*arr)
                

---

# https://www.hackerrank.com/challenges/two-characters/problem

def alternate(s):
    result = 0

    print(s)
    c = set(s)
    
    if len(c) > 2:
        for i in range(len(s)):
            dc = s[i]
            t = s.replace(dc, '')
            if len(t) > result:
                # print(" ", s, " - ", dc, " = ", t)
                l = alternate(t)
                result = max(result, l)    
    elif len(c) == 2:
        is_alternate=1
        for i in range(1,len(s)):
            if s[i] == s[i-1]:
                is_alternate=0
                break
        if is_alternate == 1:
            print("  alternate", s, len(s))
            result = len(s)

    return result

---

# https://www.hackerrank.com/challenges/pangrams/problem?isFullScreen=true

def pangrams(s):
    ps = [ chr(c) for c in range(ord('a'), ord('z')) ]
    for t in s.lower():
        if t in ps:
            ps.remove(t)
    return "pangram" if len(ps) == 0 else "not pangram"

def pangrams(s):
    ps = set([ chr(c) for c in range(ord('a'), ord('z')) ])
    return "pangram" if len(ps.difference(s.lower())) == 0 else "not pangram"


---

# Reducing set of strings to intersection of all characters across all strings

def gemstones(arr):
    sarr = list(map(set, arr))
    return len(reduce(lambda c, f: c.intersection(f), sarr))

---

# Stable sort
# https://www.hackerrank.com/challenges/countingsort4/problem?isFullScreen=true

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'countSort' function below.
#
# The function accepts 2D_STRING_ARRAY arr as parameter.
#

def countSort(arr):
    d = {}
    arr_mid = len(arr)/2
    for index, a in enumerate(arr):
        k = a[0]
        v = "-" if index < arr_mid else a[1]
        if k in d.keys():
            d[k].append(v)
        else:
            d[k] = [v]

    r = ""
    for sk in sorted(d.keys()):
        r = " ".join([r, *d[sk]])
    print(r.strip())
            

if __name__ == '__main__':
    n = int(input().strip())

    arr = []

    for _ in range(n):
        arr.append(input().rstrip().split())

    countSort(arr)