Problem I. IT over the bridge ≡

Statement

A certain large organization has an office building with an extensive local area network. Recently said organization has expanded to a new office building, where a new local area network was installed. Unfortunately, the new building is located on a remote island, and the infrastructure there is plagued by all kinds of problems: disconnects, power outages, network packet drops etc.

Engineers of the organization's IT department installed two monitoring servers, one for each building. Each server writes a log, where it stores the type of failure for every problem it detects.

In theory, both logs should be identical. However, it turned out that even the monitoring subsystem itself has issues: some problems are detected only by one server, servers sometimes erroneously report non-existing problems, and even timestamps are unreliable since server clocks are not synchronized.

Engineers decided to encode each log as a string of L lower-case Latin letters, one letter for each problem. To filter out monitoring errors, they decided to define the real problem history as the longest subsequence of problems recorded in both logs in the same order.

While trying to improve the network, engineers frequently need to compare not only the whole logs, but selected segments of them.

Given two strings a and b representing the two logs, and a sequence of N requests if the form of a₁, a₂, b₁, b₂, your program must for each request output the length of the real problem history produced by comparing the segment from position a₁ to position a₂ in the first log with the segment from position b₁ to position b₂ in the second log.

Input file format

The first two lines of input file contain strings a and b of the same length L. The third line contains integer N. Following N lines contain 4 integers each — values a_i,1 a_i,2 b_i,1 b_i,2.

Output file format

Output file must contain N integers — the real problem history lengths.

Constraints

1 ≤ L ≤ 100, 1 ≤ N ≤ 10⁶, 1 ≤ a_i,1 ≤ a_i,2 ≤ L, 1 ≤ b_i,1 ≤ b_i,2 ≤ L.

Sample tests

abcd
abcd
2
1 2 3 4
1 3 2 4

0
2

aaazaaz
zzzazzz
1
4 7 1 7

3