Equivalence of Border Networks


A network, in this problem, is an unempty set of nodes connected by edges. Each two nodes are connected by at most one edge. A network is connected, that is, there is a path between any two nodes in the network. Removal of any single edge disconnects the network.
The eccentricity of node x is the distance between x and the node most distant to x. A center of a network is a node with minimum eccentricity in the network. Any network contains either one center or two centers. In the latter case, the centers are connected by an edge.

Let e be an edge in a network N. When e is removed from N, N is split into two disjoint networks N1 and N2. Any of these networks which contains no center of the original network N is called a border network.
The root of a border network BN is the node in BN which distance to a center of N (measured in the original network N) is minimal among all nodes in BN. We denote a border network with root R by symbol B(R).
The size of a border network is the number of nodes in it.
The height of a border network BN is the maximum distance from its root to any of the leaves in BN.
A child of a node x in a border network BN is a node y which is a neighbour of x and which distance from the BN root is bigger by one than the distance of x from the BN root.

The equivalence of two border networks B1 and B2 with their respective roots R1 and R2 is defined recursively as follows:

  1. When the size of both networks B1 and B2 is 1 then B1 and B2 are equivalent.
  2. When the size of any of networks B1 and B2 is bigger than 1, then let (C1, C2, ..., Ck) (k ≥ 1) be a sequence of all children of R1.
    Then, B1 and B2 are equivalent if and only if all children of R2 can be listed in a sequence (D1, D2, ..., Dk) in such order that B(Cj) is equivalent to B(Dj), (j = 1, 2, ..., k).
    Each child has to appear in its respective sequence exactly once.


Figure 1. Schemes of border networks in networks T1 and T2 illustrating Example 1 below. The lower and the upper bound of border network size is 2 and 3, the lower and the upper bound of border network height is 1 and 1 (the height of each considered border network is exactly 1). Border networks corresponding to the given bounds are highlighted. There are 5 border networks in T2, satisfying the given bounds, to which there exists an equivalent border network in T1. Each network scheme is accompanied by its certificate.

The task

You are given two networks T1 and T2. You are also given the lower and the upper bound of the size and the lower and the upper bound of the height of border networks. Find the number of such border networks in T2 for which there exists an equivalent border network in T1 and which size and height are within the given bounds.

Input

The first input line contains four integers Nmin, Nmax, Hmin, Hmax which represent the lower and the upper bound of the size and the lower and the upper bound of the height of border networks. Next, there are two lines describing two unempty networks T1 and T2. The networks are represented by their certificates. Each certificate occupies one line, it contains only 0s and 1s and there are no other symbols on the line.
It holds, 1 ≤ Nmin ≤ Nmax ≤ 104, 0 ≤ Hmin ≤ Hmax ≤ 103. The number of nodes in each network does not exceed 3×106.

Output

The output contains one text line with one integer representing the number of such border networks in T2 which size and height are within the given bounds and for which there exists an equivalent border network in T1.


Example 1

Input
2 3 1 1
00010111000111
000010110011011000110110010110011011
Output
5
The networks and the border networks corresponding to the given bounds are depicted in Figure 1.



     

Example 2

Input
2 7 1 2
00000101100111011000011111
0000101100111000101100111000101100111000101111
Output
10
 


Figure 2. Schemes of networks T1 and T2 in Example 2. Border networks corresponding to the given bounds are highlighted. The border network with darker background highlight in T2 has no equivalent border network in T1.




     

Example 3

Input
1 8 0 3
0000001111100000111111
0000001111100000111110000011111000001111100000111111
Output
20
 


Figure 3. Schemes of networks T1 and T2 in Example 3. Border networks corresponding to the given bounds are highlighted.

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to the public data set