jasonhuh

// original source: https://gist.github.com/raviagarwal7/e85898a2f9876581f154ee4aa0f98935

import java.io.*;
import java.util.*;
import java.math.*;

public class Main
{
	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer tokenizer=null;

jasonhuh

# Original question: https://www.geeksforgeeks.org/count-pairs-in-array-whose-sum-is-divisible-by-k/
# Refactored the code to make it easier to understand

def solve(A, K):
    freq = [0]*K # Bucket of remainders
    for num in A:
        freq[num % K] += 1 # Count of remainders in each bucket
    res = 0
    for i in range(1 + len(freq)//2):
        if i == 0:

jasonhuh

from functools import reduce

def string_hash(s):
    BASE, PRIME = 26, 10**9 + 7
    return reduce(lambda x, c: (x*BASE + ord(c)) % PRIME, s, 0)

jasonhuh

class KMP:
    def partial(self, pat):
        res = [0]
        for i in range(1, len(pat)):
            j = res[-1]
            while j > 0 and pat[j] != pat[i]:
                j = res[j-1]
            res.append(j+1 if pat[j] == pat[i] else j)
        return res

jasonhuh

class Node:
    """
    Trie Node implementation. Very basic.
    """
    def __init__(self, char: str = None):
        self.children = []
        self.char = char
        self.is_end_of_word = False

class Trie:

jasonhuh

def kth_smallest(ar, k):
    def kth_smallest(lo, hi, k):
        # same as k - 1 >= 0 and k - 1 <= hi - lo
        if k > 0 and k <= hi - lo + 1: 
            p = partition(lo, hi)
            # Since array is 0-based, subtract 1 from k
            if p - lo == k - 1: 
                return ar[p]
            if p - lo > k - 1:
                return kth_smallest(lo, p - 1, k)          

jasonhuh

import random

def quick_sort(ar):
    def partition(lo, hi):
        pivot, i = ar[hi], lo
        for j in range(lo, hi):
            if ar[j] <= pivot:
               ar[i], ar[j] = ar[j], ar[i]
               i += 1
        ar[i], ar[hi] = ar[hi], ar[i]

jasonhuh

from collections import defaultdict

def topology_sort(g, V):
    def dfs(v):
        visited[v] = True
        for u in g[v]:
            if not visited[u]:
                dfs(u)                       
        stack.insert(0, v) # This is the only difference from a conventional dfs

jasonhuh

def quick_sort(ar):
    def partition(lo, hi):
        pivot = ar[(lo + hi) // 2]
        while lo <= hi:
            while ar[lo] < pivot:
                lo += 1
            while pivot < ar[hi]:
                hi -= 1
            if lo <= hi:

jasonhuh

#Source: Python algorithms

import heapq
from itertools import count

def huffman(seq, frq):
    num = count()
    trees = list(zip(frq, num, seq))
    heapq.heapify(trees)
    while len(trees) > 1: