Problem I. IT over the bridge

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  


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 a1, a2, b1, b2, your program must for each request output the length of the real problem history produced by comparing the segment from position a1 to position a2 in the first log with the segment from position b1 to position b2 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 ai,1 ai,2 bi,1 bi,2.

Output file format

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


1 ≤ L ≤ 100, 1 ≤ N ≤ 106, 1 ≤ ai,1 ≤ ai,2 ≤ L, 1 ≤ bi,1 ≤ bi,2 ≤ L.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 2 3 4
1 3 2 4
4 7 1 7

0.105s 0.009s 13