import re
from typing import List


def parse_input(s) -> List[tuple]:
    """
    Parses the search input query and creates a data structure:
    ( column_to_search_in, string_to_search, should we filter filter for quoted string)
    :param s: input string to parse
    :return: the list of the search terms to perform and where
    """

    # implementation for 'AND'
    combined_queries = s.split(' AND ')

    queries_to_perform = []

    # find content operators (e.g. "title:")
    regex = r"([a-z]+):([a-zA-Z0-9 _]+( |$))"

    for query in combined_queries:

        matches = re.finditer(regex, query, re.MULTILINE)

        for match in matches:
            query = list(match.groups())

            # match 0 is the column
            # match 1 is the string to query
            queries_to_perform.append((query[0], query[1], False))

    # assumption: quoted queries are not combined with search operators
    if not queries_to_perform:
        if s.startswith('"') and s.endswith('"'):
            s.replace('"', '')  # remove quotes
            queries_to_perform.append(('content', s, True))
        else:
            queries_to_perform.append(('content', s, False))

    return queries_to_perform