PAL distance

Let A be a finite alphabet, let C be a positive integer, let W be the set of all mutually different strings of length C over A.
We define canonical C-string over A to be a string which is a result of concatenation of all strings in W in ascending lexicographical order. We denote canonical C-string over A by the symbol K(A, C).
Example: When A = {0,1,2} and C = 2 then K(A,C) = "000102101112202122" and it is the result of concatenation "00"."01"."02"."10"."11"."12"."20"."21"."22".

Let P and L be integers for which hold inequalities P ≥ 0, L > 0, P+L ≤ length(K(A, C)). We denote by symbol SUB(A, C, P, L) the substring of K(A,C) which starts at position with index P and has length L. We suppose that the indices of symbols in K(A, C) start with 0.
Example: SUB({0,1,2}, 2, 4, 6) = "021011".

In this problem we will consider the following three edit operations on strings over alphabet A.
1. Insert operation inserts any single symbol of A at any position of string S or appends a single symbol of A to the end of S. Note that this operation increases the length of the string by 1.
2. Delete operation deletes any single symbol from an unempty string S. Note that this operation decreases the length of the string by 1. Delete operation cannot be applied to the empty string.
3. Swap operation exchanges any two neighbouring symbols in a string of length at least 2. Note that this operation does not change the length of S. Note also that when Swap operations exchanges neighbouring equal symbols the string S remains unchanged. Swap operation cannot be applied to strings of length 1 or 0.
Example: Let A = {a, b, c}, S = acbba.
The set of all possible strings obtained from S by applying one Insert operation to S is {aacbba, acabba, acbaba, acbbaa, bacbba, abcbba, acbbba, acbbab, cacbba, accbba, acbcba, acbbca, acbbac}.
The set of all possible strings obtained from S by applying one Delete to operation S is {cbba, abba, acba, acbb}.
The set of all possible strings obtained from S by applying one Swap operation to S is {cabba, abcba, acbba, acbab}.

Let S1, S2 be two strings over alphabet A. We define PAL-distance of S1 and S2 to be the minimum number of edit operations needed to transform S1 into S2. You may suppose that the edit operations are applied in any order to only one of the strings until it is equal to the other string. We denote PAL-distance of S1 and S2 by symbol PD(S1, S2).
Example: Let A = {a, b, c, d}, S1 = abcda, S2 = cabdab. PD(S1, S2) = 3. (Two Swap operations and one Insert operation are applied to S1, or equivalently, two Swap operations and one Delete operation are applied to S2.)

The task
We have to compute the PAL-distance of two given substrings of K(A, C).

Input

Input consists of single text line containing six integers |A|, C, P1, L1, P2, L2 in this order separated by one or more spaces.
We suppose 2 ≤ |A| ≤ 50, L1, L2 ≤ 104, P1+L1 ≤ min{length(K(A,C)), 109}, P2+L2 ≤ min{length(K(A,C)), 109}

Output

Output consists of single text line containing the number PD(SUB(A, C, P1, L1), SUB(A, C, P2, L2)).

Example 1

Input:
3 2 14 2 9 3
Output:
2
We include bellow for readers convenience the strings S1 and S2, we suppose alphabet A = {a, b, c}.
S1 = cb
S2 = bbc.

Example 2

Input:
2 5 18 12 12 12
Output:
6
We include bellow for readers convenience the strings S1 and S2, we suppose alphabet A = {a, b}.
S1 = bbaabaaaabab,
S2 = abaaaabbaaba.

Example 3

Input:
10 8 0 16 799999968 32
Output:
48
We include bellow for readers convenience the strings S1 and S2, we suppose alphabet A = {a, b, c, d, e, f, g, h, i, j}.
S1 = aaaaaaaaaaaaaaab,
S2 = jjjjjjjgjjjjjjjhjjjjjjjijjjjjjjj.

Example 4

Input:
10 8 300000000 5000 400000000 5000
Output:
2500

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 a stderr is available to him/her.

Public data