## 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 ≤ 10

^{4}, P1+L1 ≤ min{length(K(A,C)), 10

^{9}}, P2+L2 ≤ min{length(K(A,C)), 10

^{9}}

### 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 3Output:

2We 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 12Output:

6We 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 32Output:

48We 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 5000Output:

2500