from typing import List
from typing import Optional
from typing import Tuple


def merge_template_tokens(
    template_ids: List[int],
    token_ids: List[int],
    max_length: Optional[int] = None
) -> Tuple[List[int], List[int]]:
    """ Merge template and token ids
    Args:
      - template_ids: List[int], template ids
      - token_ids: List[int], token ids
      - max_length: int, max length
    Return:
      - token_ids: List[int], merged token ids
      - template_mask: List[int], template mask
    """
    token_ids = [token_ids[0]] + template_ids + token_ids[1:-1]
    if max_length:
        token_ids = token_ids[:max_length - 1] + [token_ids[-1]]
    template_mask = [0] + [1] * len(template_ids) + [0] * (len(token_ids) - len(template_ids) - 1)
    return token_ids,  template_mask