Longest Common Subsequence of Substrings

This problem is adapted from PA 2020 Round 4 (Tekstówka).

You are given two strings s and t consisting of lowercase English letters. For any substring defined as s_i,j (where 1 ≤ i ≤ j ≤ |s|) which denotes the consecutive characters from the i-th to the j-th character of s, and similarly t_i,j for string t, your task is to answer q queries.

Each query is given by four integers i, j, k, and l (with 1 ≤ i ≤ j ≤ |s| and 1 ≤ k ≤ l ≤ |t|). For each query, you must output a longest common subsequence (LCS) of the substrings s_i,j and t_k,l.

Note: A subsequence of a string is obtained by deleting some (or possibly none) of its characters without changing the order of the remaining characters. For example, the string potyczki can have subsequences such as tyki or pi (but not koty).

If there are multiple LCS answers, output any one of them.

inputFormat

The input consists of:

1. A line containing the string s.
2. A line containing the string t.
3. A line containing an integer q representing the number of queries.
4. q lines, each containing four integers i j k l separated by spaces.

It is guaranteed that 1 ≤ i ≤ j ≤ |s| and 1 ≤ k ≤ l ≤ |t|.

outputFormat

For each query, print a single line containing a longest common subsequence of the substrings s[i...j] and t[k...l]. If there are multiple valid answers, output any one.

sample

abcde
ace
2
1 5 1 3
2 4 1 2

ace
c