Hedro's Hexahedron

source: University of Aizu Programming Contest 2009 1

raw_problem:
Problem H: Hedro's Hexahedron

Dr. Hedro is astonished.  According to his theory, we can make sludge that can dissolve almost everything on the earth.  Now he's trying to produce the sludge to verify his theory.

The sludge is produced in a rectangular solid shaped tank whose size is N × N × 2.  Let coordinate of two corner points of tank be (-N/2, -N/2, -1), (N/2, N/2, 1) as shown in Figure 1.

Figure 1

 Doctor pours liquid that is ingredient of the sludge until height of the liquid becomes 1.  Next, he get a lid on a tank and rotates slowly, without ruffling, with respect to z axis (Figure 2).  After rotating enough long time, sludge is produced.  Volume of liquid never changes through this operation.

Figure 2

Needless to say, ordinary materials cannot be the tank.  According to Doctor's theory, there is only one material that is not dissolved by the sludge on the earth.  Doctor named it finaldefenceproblem (for short, FDP).  To attach FDP tiles inside the tank allows to produce the sludge.

Since to produce FDP is very difficult, the size of FDP tiles are limited to 1 * 1.  At first, doctor tried to cover entire the entire inside of the tank.  However, it turned out that to make enough number FDP tiles that can cover completely is impossible because it takes too long time.  Therefore, he decided to replace FDP tiles where an area the sludge touches is zero with those of ordinary materials.  All tiles are very thin, so never affects height of the sludge.

How many number of FDP tiles does doctor need?  He has imposed this tough problem on you, his helper.

Input

Input file contains several data sets.
Each data set has one integer that describes N.

Input ends when N = 0.  You should output nothing for this case.

Output

For each data set, print the number of tiles in a line.

Constraints

Judge data consists of at most 150 datasets.

2 ≤ N ≤ 1012

N is even number

Sample Input

2
4
0

Output for the Sample Input

24
64

solutions: ["# AOJ 1026 Hedro's Hexahedron\n# Python3 2018.7.5 bal4u\n\nwhile True:\n\tn = int(input())\n\tif n == 0: break\n\tans = s = n >> 1\n\ti, k = 1, 2\n\twhile i*i < s:\n\t\tans += (n+k-1)//k\n\t\ti += 1\n\t\tk += 2\n\tans = ans*2 - i*i\n\tif n & 1: ans += 1\n\tprint((ans+n) << 3)\n", "# A106633\ndef f(n):\n  res=1+2*n\n  i=1\n  while i*i<=n:\n    res+=1+(n-i*i)//i*2\n    i+=1\n  return res\n\nwhile 1:\n  n=int(input())\n  if n==0: break\n  print(8*f(n//2-1)+8*n)\n", "while 1:\n    n=int(input())\n    if n==0:break\n    a=0;i=1;b=n//2\n    while i*i<b:a+=((b-1)//i+1)-i-1;i+=1\n    a=(a+b-1)*2+i\n    print(8*(a+n))\n"]

source: aizu

question:
Problem H: Hedro's Hexahedron

Dr. Hedro is astonished.  According to his theory, we can make sludge that can dissolve almost everything on the earth.  Now he's trying to produce the sludge to verify his theory.

The sludge is produced in a rectangular solid shaped tank whose size is N × N × 2.  Let coordinate of two corner points of tank be (-N/2, -N/2, -1), (N/2, N/2, 1) as shown in Figure 1.

![image](1.png)
Figure 1

 Doctor pours liquid that is ingredient of the sludge until height of the liquid becomes 1.  Next, he get a lid on a tank and rotates slowly, without ruffling, with respect to z axis (Figure 2).  After rotating enough long time, sludge is produced.  Volume of liquid never changes through this operation.

![image](2.png)
Figure 2

Needless to say, ordinary materials cannot be the tank.  According to Doctor's theory, there is only one material that is not dissolved by the sludge on the earth.  Doctor named it finaldefenceproblem (for short, FDP).  To attach FDP tiles inside the tank allows to produce the sludge.

Since to produce FDP is very difficult, the size of FDP tiles are limited to 1 * 1.  At first, doctor tried to cover entire the entire inside of the tank.  However, it turned out that to make enough number FDP tiles that can cover completely is impossible because it takes too long time.  Therefore, he decided to replace FDP tiles where an area the sludge touches is zero with those of ordinary materials.  All tiles are very thin, so never affects height of the sludge.

How many number of FDP tiles does doctor need?  He has imposed this tough problem on you, his helper.

Input

Input file contains several data sets.
Each data set has one integer that describes N.

Input ends when N = 0.  You should output nothing for this case.

Output

For each data set, print the number of tiles in a line.

Constraints

- Judge data consists of at most 150 datasets.
- 2 ≤ N ≤ 10^{12}
- N is even number

Sample Input

2
4
0

Output for the Sample Input

24
64

image_tags:
3D Geometry
3D Geometry

data_split: test


C. Place for a Selfie

problem_index: C

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
In the first test case, both parabolas do not intersect the only given line $$$y=1\cdot x$$$, so the answer is two numbers $$$1$$$.
![image](images/cf_1805_C/1.png)
In the second test case, the line $$$y=x$$$ and the parabola $$$2x^2+5x+1$$$ intersect, and also the line $$$y=4x$$$ and the parabola $$$x^2+2x+1$$$ touch, so these pairs do not satisfy the condition. So for the first parabola, the answer is $$$1$$$ ($$$y=1x$$$), and for the second parabola — $$$4$$$.
![image](images/cf_1805_C/2.png)
In the third test set, the line and the parabola intersect, so the answer is "NO".

solutions: ["# y = ax2 + bx + c\r\n# y = kx\r\n\r\n# kx = ax2 + bx + c\r\n# ax2 + (b - k)x + c = 0\r\n# tangent is where the discriminant is 0 => (b - k) ^ 2 - 4ac = 0\r\n# b - k = +/- sqrt(4ac)\r\n# k = b +/- sqrt(4ac)\r\n\r\ndef main():\r\n    \r\n    t = int(input())\r\n    allans = []\r\n    for _ in range(t):\r\n        n, m = readIntArr()\r\n        line_ks = []\r\n        for __ in range(n):\r\n            k = int(input())\r\n            line_ks.append(k)\r\n        line_ks.sort()\r\n\r\n        for __ in range(m):\r\n            a, b, c = readIntArr()\r\n            if c <= 0:\r\n                allans.append('NO')\r\n                continue\r\n            k_low = b - (4 * a * c) ** 0.5\r\n            k_high = b + (4 * a * c) ** 0.5\r\n        \r\n            lo, hi = -1, n - 1\r\n            while lo < hi:\r\n                mid = (lo + hi + 1) // 2\r\n                if line_ks[mid] <= k_low:\r\n                    lo = mid\r\n                else:\r\n                    hi = mid - 1\r\n            if lo + 1 < n and line_ks[lo + 1] < k_high:\r\n                allans.append(f'YES\\n{line_ks[lo + 1]}')\r\n            else:\r\n                allans.append('NO')\r\n    multiLineArrayPrint(allans)\r\n\r\n    return\r\n\r\nimport sys\r\ninput=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)\r\n# input=lambda: sys.stdin.readline().rstrip(\"\\r\\n\") #FOR READING STRING/TEXT INPUTS.\r\n \r\ndef oneLineArrayPrint(arr):\r\n    print(' '.join([str(x) for x in arr]))\r\ndef multiLineArrayPrint(arr):\r\n    print('\\n'.join([str(x) for x in arr]))\r\ndef multiLineArrayOfArraysPrint(arr):\r\n    print('\\n'.join([' '.join([str(x) for x in y]) for y in arr]))\r\n \r\ndef readIntArr():\r\n    return [int(x) for x in input().split()]\r\n# def readFloatArr():\r\n#     return [float(x) for x in input().split()]\r\n \r\ndef makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])\r\n    dv=defaultValFactory;da=dimensionArr\r\n    if len(da)==1:return [dv() for _ in range(da[0])]\r\n    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]\r\n \r\ndef queryInteractive(a, b):\r\n    print('? {} {}'.format(a, b))\r\n    sys.stdout.flush()\r\n    return int(input())\r\n \r\ndef answerInteractive(ans):\r\n    print('! {}'.format(ans))\r\n    sys.stdout.flush()\r\n \r\ninf=float('inf')\r\n# MOD=10**9+7\r\n# MOD=998244353\r\n \r\nfrom math import gcd,floor,ceil\r\nimport math\r\n# from math import floor,ceil # for Python2\r\n \r\nfor _abc in range(1):\r\n    main()", "from math import sqrt\r\nfrom bisect import bisect_left, bisect_right\r\n\r\ndef solve():\r\n    n, m = map(int, input().strip().split())\r\n    ks = [int(input()) for _ in range(n)]\r\n    ms = [tuple(map(int, input().split())) for _ in range(m)]\r\n    # print(ks,ms)\r\n    ks.sort()\r\n    for i in ms:\r\n        a, b, c = i\r\n        if a * c <= 0:\r\n            print(\"NO\")\r\n            continue\r\n        s = 2*sqrt(a*c)\r\n        l, h = b - s, b + s\r\n        lef, rig = bisect_right(ks,l),bisect_left(ks,h)\r\n        # print(f'{ks=} {l=} {h=} {lef=} {rig=}')\r\n        if lef == n or rig == 0 or lef == rig:\r\n            print(\"NO\")\r\n            continue\r\n        print(\"YES\")\r\n        print(ks[lef])\r\n\r\nfor _ in range(int(input())):\r\n    solve()", "import math\r\nimport copy\r\ndef rev(s):\r\n    a=''\r\n    for i in range (1,len(s)+1):\r\n        a+=s[-i]\r\n    return a\r\n\r\ndef bse(x,l):\r\n    if len(l)==0:\r\n        return False\r\n    else:\r\n        a=0;b=len(l)-1\r\n        while (b-a)>1:\r\n            mid=(a+b)//2\r\n            if l[mid]>=x:\r\n                b=mid\r\n            else:\r\n                a=mid\r\n        if l[a]==x or l[b]==x:\r\n            return True\r\n        else:\r\n            return False\r\ndef lb(l,k):\r\n    if len(l)==0:\r\n        return 0\r\n    a=0;b=len(l)-1\r\n    while (b-a>1):\r\n        mid=(a+b)//2\r\n        if l[mid]>=k:\r\n            b=mid\r\n        else:\r\n            a=mid\r\n    if l[a]>=k:\r\n        return a\r\n    elif l[b]>=k:\r\n        return b\r\n    else:\r\n        return len(l)\r\n    \r\ndef ub(l,x):\r\n    a=0;b=len(l)-1\r\n    while (b-a)>1:\r\n        mid=(a+b)//2\r\n        if l[mid]>x:\r\n            b=mid\r\n        else:\r\n            a=mid\r\n    if l[a]>x:\r\n        return a\r\n    elif l[b]>x:\r\n        return b\r\n    else:\r\n        return len(l)\r\ndef gcd(m,n):\r\n    if m==0 or n==0:\r\n        return m+n\r\n    else:\r\n        return gcd(max(m,n)%min(m,n),min(m,n))\r\n\r\ndef lcm(m,n):\r\n    if m%n==0 or n%m==0:\r\n        return max(m,n)\r\n    else:\r\n        return (m*n)//gcd(m,n)\r\n\r\ndef find_fac(n):\r\n    l=[]\r\n    for i in range (1,math.ceil(n**0.5)):\r\n        if n%i==0:\r\n            l.append(i)\r\n            l.append(n//i)\r\n    if int(math.sqrt(n))==math.sqrt(n):\r\n        l.append(int(math.sqrt(n)))\r\n    l=sorted(l)\r\n    return l\r\ndef sm_med(l):\r\n    if len(l)%2==0:\r\n        return l[len(l)//2-1]\r\n    else:\r\n        return l[len(l)//2]\r\ndef printl(l):\r\n    for i in range(0,len(l)):\r\n        l[i]=str(l[i])\r\n    print(' '.join(l))\r\n    return None\r\ndef fastpow(a,b):\r\n    if b==0:\r\n        return 1\r\n    elif b==1:\r\n        return a\r\n    else:\r\n        if b%2==1:\r\n            return fastpow(a,b//2)*fastpow(a,b//2)*a\r\n        else:\r\n            return fastpow(a,b//2)*fastpow(a,b//2)\r\ndef distinct_elements(l):\r\n    a={}\r\n    for i in range(0,len(l)):\r\n        a[l[i]]=1\r\n    return len(a)\r\ndef regular(s):\r\n    temp=0;flag=0;tflag=0;regs=0\r\n    zp=[];regp=[0 for i in range (0,len(s))]\r\n    for i in range (0,len(s)):\r\n        if s[i]==\"(\":\r\n            temp+=1\r\n        if s[i]==\")\":\r\n            temp-=1\r\n        if temp<0:\r\n            flag=1\r\n            tflag=1\r\n        if temp==0 and i>0:\r\n            if tflag==0:\r\n                regp[i]+=1\r\n                regs+=1\r\n                zp.append(i)\r\n            else:\r\n                tflag=0\r\n                zp.append(i)\r\n    return [flag,temp,zp,regp,regs]\r\n            \r\n            \r\nt=int(input())\r\nfor _ in range (0,t):\r\n    n,m=map(int,input().split())\r\n    line=[]\r\n    for i in range (0,n):\r\n        k=int(input())\r\n        line.append(k)\r\n    line=sorted(line)\r\n    eqns=[]\r\n    for i in range(0,m):\r\n        a,b,c=map(int,input().split())\r\n        eqns.append([a,b,c])\r\n    for i in range (0,m):\r\n        if eqns[i][2]<=0:\r\n            \r\n            print(\"NO\")\r\n        else:\r\n            lo=eqns[i][1]-2*math.sqrt(eqns[i][2]*eqns[i][0])\r\n            hi=eqns[i][1]+2*math.sqrt(eqns[i][2]*eqns[i][0])\r\n            x=lb(line,hi);y=ub(line,lo)\r\n            flag=0\r\n            if (x!=0):\r\n                if line[x-1]>lo:\r\n                    flag=1\r\n                    print(\"YES\")\r\n                    print(line[x-1])\r\n                    continue\r\n            if (y!=len(line)):\r\n                if line[y]<hi:\r\n                    flag=1\r\n                    print(\"YES\")\r\n                    print(line[y])\r\n                    continue\r\n            \r\n            if flag==0:\r\n                \r\n                print(\"NO\")", "import sys\n\n# lines = sys.stdin.readlines()\n# lines = list(map(lambda x: x.strip(), lines))\n# print(lines)\n# arr = list(map(int, input().strip().split(' ')))\n\nt = int(input())\n\n# True if does not intersect\ndef test(a, b, c):\n    res = b**2 - 4*a*c\n    # print(res)\n    return res < 0\n\nfor _ in range(t):\n    n, m = map(int, input().strip().split(' '))\n    \n    ks = []\n    for _ in range(n):\n        ks.append(int(input()))\n    ks.sort()\n    \n    abcs = []\n    for _ in range(m):\n        abcs.append(map(int, input().strip().split(' ')))\n    \n    for i in range(m):\n        a, b, c = abcs[i]\n\n        if c<=0: \n            print(\"NO\")\n            continue\n\n        l, r = 0, n\n        while r-l > 1:\n            mid = (l+r)//2\n            k = ks[mid]\n            if k<= b: l = mid\n            else: r = mid\n\n        l_diff = abs(b-ks[l])\n        r_diff = abs(b-ks[r]) if r < n else 10**10\n        if l_diff < r_diff: choice = ks[l]\n        else: choice = ks[r]\n\n        # print(\"c\", choice)\n        if test(a, b-choice, c):\n            print(\"YES\")\n            print(choice)\n        else: print(\"NO\")\n    print()", "'''''''''''''''''''''''''''''\r\n Author  : man_in_errors\r\n Created : 2023-04-03 20:05:57\r\n'''''''''''''''''''''''''''''\r\nimport os,io,sys,time,random,heapq\r\nfrom itertools import permutations as p\r\nfrom random import randint as R\r\nfrom bisect import bisect_left as LB\r\nfrom sys import stdin,stdout\r\n#input = stdin.readline\r\ninput = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline\r\nstart_time = time.time()\r\nII = lambda: int(input())\r\nINS = lambda: input().strip()\r\nINSD = lambda: input().strip().decode()\r\nCI = lambda r: sorted([II() for i in range(r)])\r\nRI = lambda: [int(i) for i in input().split()]\r\nPR = lambda i: print(i,end=\" \")\r\nPI = lambda i: stdout.write(str(i)+'\\n')\r\n''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''\r\ndef solve():\r\n\tn,m= RI();l=CI(n)\r\n\twhile m:\r\n\t\ta,b,c=RI();k=LB(l,b);m-=1\r\n\t\tprint((k<n and(b-l[k])**2<4*a*c)and f'YES\\n{l[k]}'or(b-l[k-1])**2<4*a*c and f'YES\\n{l[k-1]}'or'NO')\r\n\r\n''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''\r\n#sys.stdin = open(\"input.txt\",\"r\")\r\n#sys.stdout = open(\"output.txt\",\"w\")\r\nfor _ in range(1,II()+1):\r\n    solve()\r\n#print(\"Time Elapsed :\",time.time() - start_time,\"seconds\")"]

source: codeforces

raw_problem:
C. Place for a Selfie

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

The universe is a coordinate plane. There are $$$n$$$ space highways, each of which is a straight line $$$y=kx$$$ passing through the origin $$$(0, 0)$$$. Also, there are $$$m$$$ asteroid belts on the plane, which we represent as open upwards parabolas, i. e. graphs of functions $$$y=ax^2+bx+c$$$, where $$$a > 0$$$.

You want to photograph each parabola. To do this, for each parabola you need to choose a line that does not intersect this parabola and does not touch it. You can select the same line for different parabolas. Please find such a line for each parabola, or determine that there is no such line.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains $$$2$$$ integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$) —the number of lines and parabolas, respectively.

Each of the next $$$n$$$ lines contains one integer $$$k$$$ ($$$|k| \le 10^8$$$), denoting a line that is described with the equation $$$y=kx$$$. The lines are not necessarily distinct, $$$k$$$ can be equal to $$$0$$$.

Each of the next $$$m$$$ lines contains $$$3$$$ integers $$$a$$$, $$$b$$$, and $$$c$$$ ($$$a, |b|, |c| \le 10^8$$$, $$$a > 0$$$) — coefficients of equations of the parabolas $$$ax^2+bx+c$$$. The parabolas are not necessarily distinct.

It is guaranteed that the sum $$$n$$$ over all test cases does not exceed $$$10^5$$$, and the sum $$$m$$$ over all test cases also does not exceed $$$10^5$$$.

Output

For each test case, output the answers for each parabola in the given order. If there is a line that does not intersect the given parabola and doesn't touch it, print on a separate line the word "YES", and then on a separate line the number $$$k$$$ — the coefficient of this line. If there are several answers, print any of them. If the line does not exist, print one word "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

The empty lines in the output in the example are given only for illustration, you do not need to output them (but you can).

Example

Input

5

1 2

1

1 -1 2

1 -1 3

2 2

1

4

1 2 1

2 5 1

1 1

0

1 0 0

1 1

100000000

100000000 100000000 100000000

2 3

0

2

2 2 1

1 -2 1

1 -2 -1

Output

YES
1
YES
1

YES
1
YES
4

NO

YES
100000000

YES
0
NO
NO

Note

In the first test case, both parabolas do not intersect the only given line $$$y=1\cdot x$$$, so the answer is two numbers $$$1$$$.

In the second test case, the line $$$y=x$$$ and the parabola $$$2x^2+5x+1$$$ intersect, and also the line $$$y=4x$$$ and the parabola $$$x^2+2x+1$$$ touch, so these pairs do not satisfy the condition. So for the first parabola, the answer is $$$1$$$ ($$$y=1x$$$), and for the second parabola — $$$4$$$.

In the third test set, the line and the parabola intersect, so the answer is "NO".

question:
The universe is a coordinate plane. There are $$$n$$$ space highways, each of which is a straight line $$$y=kx$$$ passing through the origin $$$(0, 0)$$$. Also, there are $$$m$$$ asteroid belts on the plane, which we represent as open upwards parabolas, i. e. graphs of functions $$$y=ax^2+bx+c$$$, where $$$a > 0$$$.
You want to photograph each parabola. To do this, for each parabola you need to choose a line that does not intersect this parabola and does not touch it. You can select the same line for different parabolas. Please find such a line for each parabola, or determine that there is no such line.

Input
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains $$$2$$$ integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$) —the number of lines and parabolas, respectively.
Each of the next $$$n$$$ lines contains one integer $$$k$$$ ($$$|k| \le 10^8$$$), denoting a line that is described with the equation $$$y=kx$$$. The lines are not necessarily distinct, $$$k$$$ can be equal to $$$0$$$.
Each of the next $$$m$$$ lines contains $$$3$$$ integers $$$a$$$, $$$b$$$, and $$$c$$$ ($$$a, |b|, |c| \le 10^8$$$, $$$a > 0$$$) — coefficients of equations of the parabolas $$$ax^2+bx+c$$$. The parabolas are not necessarily distinct.
It is guaranteed that the sum $$$n$$$ over all test cases does not exceed $$$10^5$$$, and the sum $$$m$$$ over all test cases also does not exceed $$$10^5$$$.

Output
For each test case, output the answers for each parabola in the given order. If there is a line that does not intersect the given parabola and doesn't touch it, print on a separate line the word "YES", and then on a separate line the number $$$k$$$ — the coefficient of this line. If there are several answers, print any of them. If the line does not exist, print one word "NO".
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
The empty lines in the output in the example are given only for illustration, you do not need to output them (but you can).

Example
Input
5
1 2
1
1 -1 2
1 -1 3
2 2
1
4
1 2 1
2 5 1
1 1
0
1 0 0
1 1
100000000
100000000 100000000 100000000
2 3
0
2
2 2 1
1 -2 1
1 -2 -1

Output
YES
1
YES
1

YES
1
YES
4

NO

YES
100000000

YES
0
NO
NO

Note
In the first test case, both parabolas do not intersect the only given line $$$y=1\cdot x$$$, so the answer is two numbers $$$1$$$.
 ![image](1.png) In the second test case, the line $$$y=x$$$ and the parabola $$$2x^2+5x+1$$$ intersect, and also the line $$$y=4x$$$ and the parabola $$$x^2+2x+1$$$ touch, so these pairs do not satisfy the condition. So for the first parabola, the answer is $$$1$$$ ($$$y=1x$$$), and for the second parabola — $$$4$$$.
 ![image](2.png) In the third test set, the line and the parabola intersect, so the answer is "NO".

image_tags:
2D Geometry
2D Geometry

data_split: test


Colored Cubes

source: ACM International Collegiate Programming Contest, Asia Regional 2005, Japan

raw_problem:
Problem C: Colored Cubes

There are several colored cubes. All of them are of the same size but they may be colored
differently. Each face of these cubes has a single color. Colors of distinct faces of a cube may or
may not be the same.

Two cubes are said to be identically colored if some suitable rotations of one of the cubes give
identical looks to both of the cubes. For example, two cubes shown in Figure 2 are identically
colored. A set of cubes is said to be identically colored if every pair of them are identically
colored.

A cube and its mirror image are not necessarily identically colored. For example, two cubes
shown in Figure 3 are not identically colored.

You can make a given set of cubes identically colored by repainting some of the faces, whatever
colors the faces may have. In Figure 4, repainting four faces makes the three cubes identically
colored and repainting fewer faces will never do.

Your task is to write a program to calculate the minimum number of faces that needs to be
repainted for a given set of cubes to become identically colored.

Input

The input is a sequence of datasets. A dataset consists of a header and a body appearing in this
order. A header is a line containing one positive integer n and the body following it consists
of n lines. You can assume that 1 ≤ n ≤ 4. Each line in a body contains six color names
separated by a space. A color name consists of a word or words connected with a hyphen (-).
A word consists of one or more lowercase letters. You can assume that a color name is at most
24-characters long including hyphens.

A dataset corresponds to a set of colored cubes. The integer n corresponds to the number of
cubes. Each line of the body corresponds to a cube and describes the colors of its faces. Color
names in a line is ordered in accordance with the numbering of faces shown in Figure 5. A line

      color1 color2 color3 color4 color5 color6
</pre

corresponds to a cube colored as shown in Figure 6.

The end of the input is indicated by a line containing a single zero. It is not a dataset nor a
part of a dataset.

Output

For each dataset, output a line containing the minimum number of faces that need to be repainted
to make the set of cubes identically colored.

Sample Input

3
scarlet green blue yellow magenta cyan
blue pink green magenta cyan lemon
purple red blue yellow cyan green
2
red green blue yellow magenta cyan
cyan green blue yellow magenta red
2
red green gray gray magenta cyan
cyan green gray gray magenta red
2
red green blue yellow magenta cyan
magenta red blue yellow cyan green
3
red green blue yellow magenta cyan
cyan green blue yellow magenta red
magenta red blue yellow cyan green
3
blue green green green green blue
green blue blue green green green
green green green green green sea-green
3
red yellow red yellow red yellow
red red yellow yellow red yellow
red red red red red red
4
violet violet salmon salmon salmon salmon
violet salmon salmon salmon salmon violet
violet violet salmon salmon violet violet
violet violet violet violet salmon salmon
1
red green blue yellow magenta cyan
4
magenta pink red scarlet vermilion wine-red
aquamarine blue cyan indigo sky-blue turquoise-blue
blond cream chrome-yellow lemon olive yellow
chrome-green emerald-green green olive vilidian sky-blue
0

Output for the Sample Input

4
2
0
0
2
3
4
4
0
16

input_output: {"inputs": ["2\nred green blue yellow magenta cyan\nred green blue yellow magenta cyan\n2\nred green blue yellow magenta cyan\ncyan magenta yellow blue green red\n2\nred green blue yellow magenta cyan\nred green blue cyan yellow magenta\n3\nred green blue yellow magenta cyan\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\nred blue magenta green yellow cyan\n2\nred green blue yellow magenta cyan\ncyan yellow green magenta blue red\n2\nred green blue yellow magenta cyan\nred blue yellow green cyan magenta\n3\nred blue magenta green yellow cyan\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\nred yellow green magenta blue cyan\n2\nred green blue yellow magenta cyan\ncyan blue magenta green yellow red\n2\nred green blue yellow magenta cyan\nred cyan green yellow blue magenta\n3\nred yellow green magenta blue cyan\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\nred magenta yellow blue green cyan\n2\nred green blue yellow magenta cyan\ncyan green blue yellow magenta red\n2\nred green blue yellow magenta cyan\nred yellow cyan blue green magenta\n3\nred magenta yellow blue green cyan\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\ngreen red yellow blue cyan magenta\n2\nred green blue yellow magenta cyan\nmagenta cyan blue yellow red green\n2\nred green blue yellow magenta cyan\ngreen red cyan blue magenta yellow\n3\ngreen red yellow blue cyan magenta\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\ngreen blue red cyan yellow magenta\n2\nred green blue yellow magenta cyan\nmagenta yellow cyan red blue green\n2\nred green blue yellow magenta cyan\ngreen blue red magenta cyan yellow\n3\ngreen blue red cyan yellow magenta\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\ngreen yellow cyan red blue magenta\n2\nred green blue yellow magenta cyan\nmagenta blue red cyan yellow green\n2\nred green blue yellow magenta cyan\ngreen cyan magenta red blue yellow\n3\ngreen yellow cyan red blue magenta\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\ngreen cyan blue yellow red magenta\n2\nred green blue yellow magenta cyan\nmagenta red yellow blue cyan green\n2\nred green blue yellow magenta cyan\ngreen magenta blue cyan red yellow\n3\ngreen cyan blue yellow red magenta\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\nblue red green magenta cyan yellow\n2\nred green blue yellow magenta cyan\nyellow cyan magenta green red blue\n2\nred green blue yellow magenta cyan\nblue red green yellow magenta cyan\n3\nblue red green magenta cyan yellow\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\nblue green cyan red magenta yellow\n2\nred green blue yellow magenta cyan\nyellow magenta red cyan green blue\n2\nred green blue yellow magenta cyan\nblue green magenta red yellow cyan\n3\nblue green cyan red magenta yellow\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\nblue magenta red cyan green yellow\n2\nred green blue yellow magenta cyan\nyellow green cyan red magenta blue\n2\nred green blue yellow magenta cyan\nblue yellow red magenta green cyan\n3\nblue magenta red cyan green yellow\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\nblue cyan magenta green red yellow\n2\nred green blue yellow magenta cyan\nyellow red green magenta cyan blue\n2\nred green blue yellow magenta cyan\nblue magenta yellow green red cyan\n3\nblue cyan magenta green red yellow\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\nyellow red magenta green cyan blue\n2\nred green blue yellow magenta cyan\nblue cyan green magenta red yellow\n2\nred green blue yellow magenta cyan\ncyan red yellow green magenta blue\n3\nyellow red magenta green cyan blue\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\nyellow green red cyan magenta blue\n2\nred green blue yellow magenta cyan\nblue magenta cyan red green yellow\n2\nred green blue yellow magenta cyan\ncyan green red magenta yellow blue\n3\nyellow green red cyan magenta blue\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\nyellow magenta cyan red green blue\n2\nred green blue yellow magenta cyan\nblue green red cyan magenta yellow\n2\nred green blue yellow magenta cyan\ncyan yellow magenta red green blue\n3\nyellow magenta cyan red green blue\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\nyellow cyan green magenta red blue\n2\nred green blue yellow magenta cyan\nblue red magenta green cyan yellow\n2\nred green blue yellow magenta cyan\ncyan magenta green yellow red blue\n3\nyellow cyan green magenta red blue\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\nmagenta red blue yellow cyan green\n2\nred green blue yellow magenta cyan\ngreen cyan yellow blue red magenta\n2\nred green blue yellow magenta cyan\nyellow red blue cyan magenta green\n3\nmagenta red blue yellow cyan green\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\nmagenta blue cyan red yellow green\n2\nred green blue yellow magenta cyan\ngreen yellow red cyan blue magenta\n2\nred green blue yellow magenta cyan\nyellow blue magenta red cyan green\n3\nmagenta blue cyan red yellow green\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\nmagenta yellow red cyan blue green\n2\nred green blue yellow magenta cyan\ngreen blue cyan red yellow magenta\n2\nred green blue yellow magenta cyan\nyellow cyan red magenta blue green\n3\nmagenta yellow red cyan blue green\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\nmagenta cyan yellow blue red green\n2\nred green blue yellow magenta cyan\ngreen red blue yellow cyan magenta\n2\nred green blue yellow magenta cyan\nyellow magenta cyan blue red green\n3\nmagenta cyan yellow blue red green\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\ncyan green yellow blue magenta red\n2\nred green blue yellow magenta cyan\nred magenta blue yellow green cyan\n2\nred green blue yellow magenta cyan\nmagenta green cyan blue yellow red\n3\ncyan green yellow blue magenta red\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\ncyan blue green magenta yellow red\n2\nred green blue yellow magenta cyan\nred yellow magenta green blue cyan\n2\nred green blue yellow magenta cyan\nmagenta blue green yellow cyan red\n3\ncyan blue green magenta yellow red\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\ncyan yellow magenta green blue red\n2\nred green blue yellow magenta cyan\nred blue green magenta yellow cyan\n2\nred green blue yellow magenta cyan\nmagenta cyan yellow green blue red\n3\ncyan yellow magenta green blue red\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n2\nred green blue yellow magenta cyan\ncyan magenta blue yellow green red\n2\nred green blue yellow magenta cyan\nred green yellow blue magenta cyan\n2\nred green blue yellow magenta cyan\nmagenta yellow blue cyan green red\n3\ncyan magenta blue yellow green red\ncyan magenta yellow blue green red\nred green blue cyan yellow magenta\n3\nblue green cyan red magenta yellow\ndark-sky-blue blue sky-blue dark-blue light-sky-blue light-blue\nlight-red light-yellow light-green light-magenta light-blue light-cyan\n2\nindigo-blue indigo-blue indigo-blue indigo-blue indigo-blue indigo-blue\nindigo-blue indigo-blue indigo-blue indigo-blue indigo-blue indigo-blue\n3\npurple purple purple purple purple purple\npurple purple purple purple purple purple\npurple purple purple purple purple purple\n4\nblue blue blue blue blue blue\nblue blue blue blue blue blue\nblue blue blue blue blue blue\nblue blue blue blue blue blue\n2\nyellow green red cyan magenta blue\nlight-blue light-sky-blue sky-blue dark-blue blue dark-sky-blue\n3\nlight-sky-blue sky-blue light-blue dark-sky-blue dark-blue blue\nseashell snow ivory lavender misty-rose mint-cream\nvermilion salmon red brown scarlet pink\n4\ngreen blue red cyan yellow magenta\nlight-cyan light-magenta light-blue light-yellow light-green light-red\ndark-yellow dark-green dark-red dark-cyan dark-magenta dark-blue\nsnow mint-cream ivory lavender seashell misty-rose\n4\nmagenta blue cyan red yellow green\nred scarlet vermilion pink salmon brown\ndark-yellow dark-red dark-magenta dark-green dark-cyan dark-blue\nseashell lavender snow misty-rose ivory mint-cream\n3\nyellow magenta cyan red green blue\nmagenta magenta blue yellow green red\nyellow red magenta green red blue\n4\ngreen blue red cyan yellow magenta\nred blue red blue red blue\nred red red cyan cyan cyan\nblue red green green red blue\n4\nred red red white white white\npink white white pink pink white\nwhite pink pink white white pink\nwhite white white pink pink pink\n4\nblue blue black blue black black\nblack black sky-blue black sky-blue sky-blue\nblack blue black blue black blue\nblack black black sky-blue sky-blue sky-blue\n4\ngreen yellow yellow green green yellow\ngreen lemon green lemon green lemon\ngreen green yellow green yellow yellow\ngreen khaki khaki green green khaki\n2\nlight-blue light-sky-blue sky-blue dark-blue blue dark-sky-blue\nred pink scarlet salmon vermilion brown\n3\ndark-blue light-blue blue light-sky-blue dark-sky-blue sky-blue\nlight-blue light-red light-green light-magenta light-cyan light-yellow\ndark-blue dark-red dark-green dark-magenta dark-cyan dark-yellow\n1\nred red red red red red\n2\nred red red red red red\nred red red red red red\n3\nred red red red red red\nred red red red red red\nred red red red red red\n4\nred red red red red red\nred red red red red red\nred red red red red red\nred red red red red red\n1\nred red red red red red\n2\nred red red red red red\nvermilion vermilion vermilion vermilion vermilion vermilion\n3\nred red red red red red\nvermilion vermilion vermilion vermilion vermilion vermilion\nsalmon salmon salmon salmon salmon salmon\n4\nred red red red red red\nvermilion vermilion vermilion vermilion vermilion vermilion\nsalmon salmon salmon salmon salmon salmon\nscarlet scarlet scarlet scarlet scarlet scarlet\n1\ncyan blue yellow black white green\n2\nblack yellow white black yellow yellow\ngreen red white white yellow blue\n3\nred black red green blue magenta\nwhite green green yellow black yellow\nmagenta yellow cyan red blue cyan\n4\ngreen red red red black yellow\nyellow white yellow blue white white\nmagenta white cyan magenta red red\nred white green blue yellow white\n1\ncyan white yellow yellow white cyan\n2\nred red cyan red green magenta\nmagenta magenta yellow white white blue\n3\nblack yellow green magenta red blue\nmagenta red green cyan blue magenta\ncyan red magenta red yellow yellow\n4\ncyan yellow magenta blue yellow cyan\nblack white green blue white red\nmagenta cyan magenta black green magenta\nred cyan magenta green yellow white\n1\nblack red white blue red blue\n2\ncyan cyan cyan green white red\nblack black red red red white\n3\nred magenta magenta magenta blue black\nred blue yellow cyan magenta black\nmagenta blue black yellow magenta black\n4\ncyan green yellow blue yellow yellow\nblue green green blue green green\ngreen blue cyan black black red\nmagenta white blue white magenta black\n1\nblack red red magenta yellow magenta\n2\nyellow red black black blue green\ngreen magenta blue blue white magenta\n3\nyellow red black green black magenta\ngreen blue yellow yellow blue white\nblue red white blue magenta blue\n4\nwhite white blue cyan black magenta\nblack white green red blue red\nmagenta cyan red blue black white\nwhite white green blue yellow yellow\n1\nblue cyan yellow green white red\n2\nmagenta black white black yellow cyan\nyellow green cyan magenta blue white\n3\nmagenta black magenta magenta green yellow\nyellow red blue cyan blue cyan\nred magenta blue magenta black blue\n4\nmagenta blue red yellow red magenta\ngreen yellow cyan black white white\ncyan yellow black green red white\nmagenta yellow white white red green\n1\nmagenta green black white cyan magenta\n2\ngreen green black green magenta black\ncyan cyan blue yellow yellow green\n3\nblue red cyan red blue cyan\nwhite black red black cyan green\nred blue blue black green white\n4\nblue blue red red yellow magenta\nblack green blue red magenta cyan\nblue black black white white red\nmagenta black black magenta cyan magenta\n1\ncyan cyan black white yellow white\n2\nblack cyan green black cyan magenta\nyellow yellow cyan cyan magenta green\n3\nblue black red red cyan white\nred green cyan white cyan blue\nyellow yellow white green blue blue\n4\nred green white green white magenta\ncyan blue red yellow white magenta\nmagenta blue blue magenta blue white\nyellow yellow red green blue cyan\n1\nyellow cyan red yellow black yellow\n2\ncyan black magenta cyan white yellow\ngreen magenta black green white cyan\n3\ncyan magenta white white red blue\nblack magenta cyan black cyan white\nmagenta red magenta magenta yellow blue\n4\nwhite green red yellow black white\nwhite white yellow cyan green yellow\nblue black white blue black white\nmagenta magenta yellow green yellow red\n1\nred white green magenta yellow magenta\n2\nblack yellow cyan black black yellow\ncyan cyan yellow red blue magenta\n3\nyellow cyan blue blue white red\nblue yellow cyan cyan magenta red\nblack magenta white white red blue\n4\nyellow black cyan green magenta magenta\nmagenta green green white green magenta\nyellow cyan green black white red\nblack green yellow yellow white white\n1\nyellow cyan yellow blue magenta yellow\n2\ncyan white green blue red cyan\nblack cyan black red magenta white\n3\nmagenta red magenta cyan black magenta\ncyan magenta cyan red red magenta\nwhite yellow green blue black cyan\n4\ncyan yellow cyan black cyan cyan\nyellow magenta blue green magenta white\nred red white cyan cyan cyan\ngreen blue green black blue green\n4\nvery-long-color-name-abc very-long-color-name-ijk very-long-color-name-pqr very-long-color-name-fgh very-long-color-name-lmn very-long-color-name-xyz\nvery-long-color-name-def very-long-color-name-ijk very-long-color-name-abc very-long-color-name-xyz very-long-color-name-lmn very-long-color-name-rst\nvery-long-color-name-hkl very-long-color-name-xyz very-long-color-name-uvw very-long-color-name-lmn very-long-color-name-abc very-long-color-name-pqr\nvery-long-color-name-xyz very-long-color-name-abc very-long-color-name-abc very-long-color-name-xyz very-long-color-name-xyz very-long-color-name-abc\n0\n"], "outputs": ["0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n0\n2\n3\n5\n10\n0\n0\n0\n5\n12\n18\n17\n2\n9\n3\n6\n6\n6\n10\n0\n0\n0\n0\n0\n6\n12\n18\n0\n4\n7\n9\n0\n5\n6\n11\n0\n4\n4\n11\n0\n4\n6\n8\n0\n3\n6\n8\n0\n5\n6\n9\n0\n2\n6\n10\n0\n3\n7\n10\n0\n4\n6\n9\n0\n4\n6\n12\n8\n"]}

source: aizu

question:
Problem C: Colored Cubes

There are several colored cubes. All of them are of the same size but they may be colored
differently. Each face of these cubes has a single color. Colors of distinct faces of a cube may or
may not be the same.

Two cubes are said to be identically colored if some suitable rotations of one of the cubes give
identical looks to both of the cubes. For example, two cubes shown in Figure 2 are identically
colored. A set of cubes is said to be identically colored if every pair of them are identically
colored.

A cube and its mirror image are not necessarily identically colored. For example, two cubes
shown in Figure 3 are not identically colored.

You can make a given set of cubes identically colored by repainting some of the faces, whatever
colors the faces may have. In Figure 4, repainting four faces makes the three cubes identically
colored and repainting fewer faces will never do.

Your task is to write a program to calculate the minimum number of faces that needs to be
repainted for a given set of cubes to become identically colored.

Input

The input is a sequence of datasets. A dataset consists of a header and a body appearing in this
order. A header is a line containing one positive integer n and the body following it consists
of n lines. You can assume that 1 ≤ n ≤ 4. Each line in a body contains six color names
separated by a space. A color name consists of a word or words connected with a hyphen (-).
A word consists of one or more lowercase letters. You can assume that a color name is at most
24-characters long including hyphens.

A dataset corresponds to a set of colored cubes. The integer n corresponds to the number of
cubes. Each line of the body corresponds to a cube and describes the colors of its faces. Color
names in a line is ordered in accordance with the numbering of faces shown in Figure 5. A line

_{1} _{2} _{3} _{4} _{5} _{6}

corresponds to a cube colored as shown in Figure 6.

The end of the input is indicated by a line containing a single zero. It is not a dataset nor a
part of a dataset.

![image](1.png)
![image](2.png)
![image](3.png)

Output

For each dataset, output a line containing the minimum number of faces that need to be repainted
to make the set of cubes identically colored.

Sample Input

3
scarlet green blue yellow magenta cyan
blue pink green magenta cyan lemon
purple red blue yellow cyan green
2
red green blue yellow magenta cyan
cyan green blue yellow magenta red
2
red green gray gray magenta cyan
cyan green gray gray magenta red
2
red green blue yellow magenta cyan
magenta red blue yellow cyan green
3
red green blue yellow magenta cyan
cyan green blue yellow magenta red
magenta red blue yellow cyan green
3
blue green green green green blue
green blue blue green green green
green green green green green sea-green
3
red yellow red yellow red yellow
red red yellow yellow red yellow
red red red red red red
4
violet violet salmon salmon salmon salmon
violet salmon salmon salmon salmon violet
violet violet salmon salmon violet violet
violet violet violet violet salmon salmon
1
red green blue yellow magenta cyan
4
magenta pink red scarlet vermilion wine-red
aquamarine blue cyan indigo sky-blue turquoise-blue
blond cream chrome-yellow lemon olive yellow
chrome-green emerald-green green olive vilidian sky-blue
0

Output for the Sample Input

4
2
0
0
2
3
4
4
0
16

image_tags:
3D Geometry
3D Geometry
3D Geometry

data_split: test


C. Optimal Sum

problem_index: C

time_limit: 2 seconds

memory_limit: 256 megabytes

question:
And here goes another problem on arrays. You are given positive integer len and array a which consists of n integers a_{1}, a_{2}, ..., a_{n}. Let's introduce two characteristics for the given array.
 -  Let's consider an arbitrary interval of the array with length len, starting in position i. Value ![image](1.png), is the modular sum on the chosen interval. In other words, the modular sum is the sum of integers on the chosen interval with length len, taken in its absolute value.-  Value ![image](2.png) is the optimal sum of the array. In other words, the optimal sum of an array is the maximum of all modular sums on various intervals of array with length len. Your task is to calculate the optimal sum of the given array a. However, before you do the calculations, you are allowed to produce no more than k consecutive operations of the following form with this array: one operation means taking an arbitrary number from array a_{i} and multiply it by -1. In other words, no more than k times you are allowed to take an arbitrary number a_{i} from the array and replace it with  - a_{i}. Each number of the array is allowed to choose an arbitrary number of times.
Your task is to calculate the maximum possible optimal sum of the array after at most k operations described above are completed.

Input
The first line contains two integers n, len (1 ≤ len ≤ n ≤ 10^{5}) — the number of elements in the array and the length of the chosen subinterval of the array, correspondingly.
The second line contains a sequence consisting of n integers a_{1}, a_{2}, ..., a_{n} (|a_{i}| ≤ 10^{9}) — the original array.
The third line contains a single integer k (0 ≤ k ≤ n) — the maximum allowed number of operations.
All numbers in lines are separated by a single space.

Output
In a single line print the maximum possible optimal sum after no more than k acceptable operations are fulfilled.
Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Examples
Input
5 3
0 -2 3 -5 1
2

Output
10

Input
5 2
1 -3 -10 4 1
3

Output
14

Input
3 3
-2 -5 4
1

Output
11

difficulty: HARD

source: codeforces

raw_problem:
C. Optimal Sum

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

And here goes another problem on arrays. You are given positive integer len and array a which consists of n integers a1, a2, ..., an. Let's introduce two characteristics for the given array.

 Let's consider an arbitrary interval of the array with length len, starting in position i. Value , is the modular sum on the chosen interval. In other words, the modular sum is the sum of integers on the chosen interval with length len, taken in its absolute value.

 Value  is the optimal sum of the array. In other words, the optimal sum of an array is the maximum of all modular sums on various intervals of array with length len.

Your task is to calculate the optimal sum of the given array a. However, before you do the calculations, you are allowed to produce no more than k consecutive operations of the following form with this array: one operation means taking an arbitrary number from array ai and multiply it by -1. In other words, no more than k times you are allowed to take an arbitrary number ai from the array and replace it with  - ai. Each number of the array is allowed to choose an arbitrary number of times.

Your task is to calculate the maximum possible optimal sum of the array after at most k operations described above are completed.

Input

The first line contains two integers n, len (1 ≤ len ≤ n ≤ 105) — the number of elements in the array and the length of the chosen subinterval of the array, correspondingly.

The second line contains a sequence consisting of n integers a1, a2, ..., an (|ai| ≤ 109) — the original array.

The third line contains a single integer k (0 ≤ k ≤ n) — the maximum allowed number of operations.

All numbers in lines are separated by a single space.

Output

In a single line print the maximum possible optimal sum after no more than k acceptable operations are fulfilled.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Examples

Input

5 3
0 -2 3 -5 1
2

Output

10

Input

5 2
1 -3 -10 4 1
3

Output

14

Input

3 3
-2 -5 4
1

Output

11

tags: ['Data structures', 'Greedy algorithms']

image_tags: Math Math

data_split: test


C. E-reader Display

problem_index: C

time_limit: 2 seconds

memory_limit: 256 megabytes

difficulty: HARD

source: codeforces

raw_problem:
C. E-reader Display

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

After years of hard work scientists invented an absolutely new e-reader display. The new display has a larger resolution, consumes less energy and its production is cheaper. And besides, one can bend it. The only inconvenience is highly unusual management. For that very reason the developers decided to leave the e-readers' software to programmers.

The display is represented by n × n square of pixels, each of which can be either black or white. The display rows are numbered with integers from 1 to n upside down, the columns are numbered with integers from 1 to n from the left to the right. The display can perform commands like "x, y". When a traditional display fulfills such command, it simply inverts a color of (x, y), where x is the row number and y is the column number. But in our new display every pixel that belongs to at least one of the segments (x, x) - (x, y) and (y, y) - (x, y) (both ends of both segments are included) inverts a color.

For example, if initially a display 5 × 5 in size is absolutely white, then the sequence of commands (1, 4), (3, 5), (5, 1), (3, 3) leads to the following changes:

You are an e-reader software programmer and you should calculate minimal number of commands needed to display the picture. You can regard all display pixels as initially white.

Input

The first line contains number n (1 ≤ n ≤ 2000).

Next n lines contain n characters each: the description of the picture that needs to be shown. "0" represents the white color and "1" represents the black color.

Output

Print one integer z — the least number of commands needed to display the picture.

Examples

Input

5
01110
10010
10001
10011
11110

Output

4

question:
After years of hard work scientists invented an absolutely new e-reader display. The new display has a larger resolution, consumes less energy and its production is cheaper. And besides, one can bend it. The only inconvenience is highly unusual management. For that very reason the developers decided to leave the e-readers' software to programmers.
The display is represented by n × n square of pixels, each of which can be either black or white. The display rows are numbered with integers from 1 to n upside down, the columns are numbered with integers from 1 to n from the left to the right. The display can perform commands like "x, y". When a traditional display fulfills such command, it simply inverts a color of (x, y), where x is the row number and y is the column number. But in our new display every pixel that belongs to at least one of the segments (x, x) - (x, y) and (y, y) - (x, y) (both ends of both segments are included) inverts a color.
For example, if initially a display 5 × 5 in size is absolutely white, then the sequence of commands (1, 4), (3, 5), (5, 1), (3, 3) leads to the following changes:
 ![image](1.png) You are an e-reader software programmer and you should calculate minimal number of commands needed to display the picture. You can regard all display pixels as initially white.

Input
The first line contains number n (1 ≤ n ≤ 2000).
Next n lines contain n characters each: the description of the picture that needs to be shown. "0" represents the white color and "1" represents the black color.

Output
Print one integer z — the least number of commands needed to display the picture.

Examples
Input
5
01110
10010
10001
10011
11110

Output
4

tags: ['Greedy algorithms', 'Constructive algorithms']

skill_types: ['Greedy algorithms']

data_split: test


difficulty: HARD

name: Association for Cool Machineries (Part 1)

source: open kattis

raw_problem:
You are the boss of ACM
    (Association for Cool Machineries), an upstanding company with
    a single goal of world domination.

Like all other world domination oriented villains, you dream
    of having a gigantic evil robot doing evil deeds. I mean, is
    there anyone who can resist the urge of having your own
    personal gigantic laser-firing robot? Thus, it is to your
    ultimate joy when the scientific committee of ACM told you about their success in inventing
    a prototype for the GL-bot (shorthand for Giant Laser
    Robot).

As a demonstration, they have placed GL-bot on a field
    modeled as an $N \times N$
    grid. Each cell in the grid is either empty or impassable. All
    cells on the borders of the grid are impassable. GL-bot is
    initially located on one of these empty cells.

The GL-bot’s behavior is programmed with a string of length
    at most $N$. Each
    character in the string is either <tt class="ttfamily"><</tt>, <tt class="ttfamily">></tt>,
    <tt class="ttfamily">^</tt>, or <tt class="ttfamily">v</tt>,
    denoting four directions of movement. GL-bot will continuously
    move on the grid according to this string. The movement works
    as follows. GL-bot considers the characters in the string one
    by one, starting from the first character until the last
    character, and then loop back to the first character and
    repeat. GL-bot performs a movement depending on the character
    being considered (for the images below, black cells denote
    impassable cells, while white cells denote empty cells):

<tt class="ttfamily"><</tt>: GL-bot moves to the left
        one step, if able.

<tt class="ttfamily">></tt>: GL-bot moves to the
        right one step, if able.

<tt class="ttfamily">v</tt>: GL-bot moves down one step,
        if able.

<tt class="ttfamily">^</tt>: GL-bot moves up one step,
        if able.

More specifically, GL-bot moves one cell from its current
    location to the location as determined by the character.
    However, if the new location is impassable, the robot does not
    perform the move, and this movement is skipped. GL-bot then
    considers the next character in the program.

The trail of GL-bot is the (possibly infinite) sequence of
    (possibly non-distinct) cells of the grid that GL-bot traverses
    in order. The trail can be viewed to be generated as follows:
    initially, before GL-bot performs any movement, the trail
    contains one element: the initial location of GL-bot. Whenever
    GL-bot moves into a different cell, the new location of GL-bot
    is added to the trail. In particular, this implies that no two
    consecutive cells in the trail are the same — if the robot is
    unable to move in a particular direction because it was
    occupied by an impassable cell, the trail is not extended.

You giggle giddily as you watch GL-bot move. For some
    program and for some grid configuration, GL-bot will never stop
    moving, no matter how long time has passed. It can be proven
    that in this case, the trail will eventually end up repeating a
    continuous subsequence of itself. But you…, you don’t see such
    a thing. What you see is a robot that moves perpetually, as if
    it is sapient. Your fascination with GL-bot leaves the
    scientific committee worried, as GL-bot is not actually sapient
    yet (it just needs a few more tweaks). Thus, they attempt to
    convince you by showing that the movement is simply follows a
    pattern. If the length of the trail of the robot is finite, you
    should output $1$.
    Otherwise, let $X$ be the
    smallest integer such that the suffix of the trail will be a
    repetition of a continuous subsequence of the trail of length
    exactly $X$. Find
    $X$.

Input

The first line contains a non-negative integer $3 \leq N \leq 200$, denoting both the
    dimension of the field and the maximum possible length of
    GL-bot’s program.

The next line contains a non-empty string of length at most
    $N$, consisting only of
    the characters <tt class="ttfamily"><</tt>, <tt class="ttfamily">></tt>, <tt class="ttfamily">^</tt>, and
    <tt class="ttfamily">v</tt>. This string denotes GL-bot’s
    program.

Thereafter follows $N$
    lines, each consists of a string consisting of $N$ characters. Each line describes a
    row of the grid — the $j$-th character of the $i$-th line denotes the content of the
    cell located at the $i$-th
    row from the top and $j$-th column from the left, and is
    either one of these:

<tt class="ttfamily">#</tt>: denotes an impassable
        cell.

<tt class="ttfamily">.</tt>: denotes an empty cell.

<tt class="ttfamily">R</tt>: denotes an empty cell on
        which the robot initially resides.

It is guaranteed that the grid will contain exactly one
    character R, and that the first and final rows and columns
    consist entirely of the character <tt class="ttfamily">#</tt>.

Output

If the robot’s trail is of finite length, print a single
    integer $1$. Otherwise,
    print a single integer $X$
    as described in the problem statement.

Sample Data Explanation

In the first example, the trail of the robot is illustrated
    as follows:

Hence, $X=2$ in this
    case.

Sample Input 1
Sample Output 1

6
>^<^
######
#.#..#
#....#
#..R.#
#....#
######

2

Sample Input 2
Sample Output 2

4
v<^>
####
#.R#
#..#
####

4

Sample Input 3
Sample Output 3

4
<<<
####
#.R#
#..#
####

1

Sample Input 4
Sample Output 4

5
<<>>
#####
#R..#
#####
#####
#####

4

question:
You are the boss ofACM(Association for Cool Machineries), an upstanding company with a single goal of world domination.
Like all other world domination oriented villains, you dream of having a gigantic evil robot doing evil deeds. I mean, is there anyone who can resist the urge of having your own personal gigantic laser-firing robot? Thus, it is to your ultimate joy when the scientific committee ofACMtold you about their success in inventing a prototype for the GL-bot (shorthand for Giant Laser Robot).
As a demonstration, they have placed GL-bot on a field modeled as an$N \times N$grid. Each cell in the grid is either empty or impassable. All cells on the borders of the grid are impassable. GL-bot is initially located on one of these empty cells.
The GL-bot’s behavior is programmed with a string of length at most$N$. Each character in the string is either<,>,^, orv, denoting four directions of movement. GL-bot will continuously move on the grid according to this string. The movement works as follows. GL-bot considers the characters in the string one by one, starting from the first character until the last character, and then loop back to the first character and repeat. GL-bot performs a movement depending on the character being considered (for the images below, black cells denote impassable cells, while white cells denote empty cells):
- <: GL-bot moves to the left one step, if able. ![image](1.png)- >: GL-bot moves to the right one step, if able. ![image](2.png)- v: GL-bot moves down one step, if able. ![image](3.png)- ^: GL-bot moves up one step, if able. ![image](4.png)
More specifically, GL-bot moves one cell from its current location to the location as determined by the character. However, if the new location is impassable, the robot does not perform the move, and this movement is skipped. GL-bot then considers the next character in the program.
The trail of GL-bot is the (possibly infinite) sequence of (possibly non-distinct) cells of the grid that GL-bot traverses in order. The trail can be viewed to be generated as follows: initially, before GL-bot performs any movement, the trail contains one element: the initial location of GL-bot. Whenever GL-bot moves into a different cell, the new location of GL-bot is added to the trail. In particular, this implies that no two consecutive cells in the trail are the same — if the robot is unable to move in a particular direction because it was occupied by an impassable cell, the trail is not extended.
You giggle giddily as you watch GL-bot move. For some program and for some grid configuration, GL-bot will never stop moving, no matter how long time has passed. It can be proven that in this case, the trail will eventually end up repeating a continuous subsequence of itself. But you…, you don’t see such a thing. What you see is a robot that moves perpetually, as if it is sapient. Your fascination with GL-bot leaves the scientific committee worried, as GL-bot is not actually sapient yet (it just needs a few more tweaks). Thus, they attempt to convince you by showing that the movement is simply follows a pattern. If the length of the trail of the robot is finite, you should output$1$. Otherwise, let$X$be the smallest integer such that the suffix of the trail will be a repetition of a continuous subsequence of the trail of length exactly$X$. Find$X$.

Input
The first line contains a non-negative integer$3 \leq N \leq 200$, denoting both the dimension of the field and the maximum possible length of GL-bot’s program.
The next line contains a non-empty string of length at most$N$, consisting only of the characters<,>,^, andv. This string denotes GL-bot’s program.
Thereafter follows$N$lines, each consists of a string consisting of$N$characters. Each line describes a row of the grid — the$j$-th character of the$i$-th line denotes the content of the cell located at the$i$-th row from the top and$j$-th column from the left, and is either one of these:
- #: denotes an impassable cell.- .: denotes an empty cell.- R: denotes an empty cell on which the robot initially resides.
It is guaranteed that the grid will contain exactly one character R, and that the first and final rows and columns consist entirely of the character#.

Output
If the robot’s trail is of finite length, print a single integer$1$. Otherwise, print a single integer$X$as described in the problem statement.
Sample Data ExplanationIn the first example, the trail of the robot is illustrated as follows:
![image](5.png)
Hence,$X=2$in this case.
Sample Input 1
6
>^<^
######
#.#..#
#....#
#..R.#
#....#
######

Sample Output 1
2

Sample Input 2
4
v<^>
####
#.R#
#..#
####

Sample Output 2
4

Sample Input 3
4
<<<
####
#.R#
#..#
####

Sample Output 3
1

Sample Input 4
5
<<>>
#####
#R..#
#####
#####
#####

Sample Output 4
4

image_tags: Map Map Map Map Map

data_split: test


Routing a Marathon Race

source: ACM International Collegiate Programming Contest, Asia Regional 2015, Japan

raw_problem:
Problem I
Routing a Marathon Race

As a member of the ICPC (Ibaraki Committee of Physical Competitions), you are responsible for planning the route of a marathon event held in the City of Tsukuba. A great number of runners, from beginners to experts, are expected to take part.

You have at hand a city map that lists all the street segments suited for the event and all the junctions on them. The race is to start at the junction in front of Tsukuba High, and the goal is at the junction in front of City Hall, both of which are marked on the map.

To avoid congestion and confusion of runners of divergent skills, the route should not visit the same junction twice. Consequently, although the street segments can be used in either direction, they can be included at most once in the route. As the main objective of the event is in recreation and health promotion of citizens, time records are not important and the route distance can be arbitrarily decided.

A number of personnel have to be stationed at every junction on the route. Junctions adjacent to them, i.e., junctions connected directly by a street segment to the junctions on the route, also need personnel staffing to keep casual traffic from interfering the race. The same number of personnel is required when a junction is on the route and when it is adjacent to one, but different junctions require different numbers of personnel depending on their sizes and shapes, which are also indicated on the map.

The municipal authorities are eager in reducing the costs including the personnel expense for
events of this kind. Your task is to write a program that plans a route with the minimum
possible number of personnel required and outputs that number.

Input

The input consists of a single test case representing a summary city map, formatted as follows.

$n$ $m$

$c_1$

...

$c_n$

$i_1$ $j_1$

...

$i_m$ $j_m$

The first line of a test case has two positive integers, $n$ and $m$. Here, $n$ indicates the number of junctions in the map $(2 \leq n \leq 40)$, and $m$ is the number of street segments connecting adjacent junctions. Junctions are identified by integers 1 through $n$.

Then comes $n$ lines indicating numbers of personnel required. The $k$-th line of which, an integer $c_k$ $(1 \leq c_k \leq 100)$, is the number of personnel required for the junction $k$.

The remaining $m$ lines list street segments between junctions. Each of these lines has two integers $i_k$ and $j_k$, representing a segment connecting junctions $i_k$ and $j_k$ $(i_k \ne j_k)$. There is at most one street segment connecting the same pair of junctions.

The race starts at junction 1 and the goal is at junction $n$. It is guaranteed that there is at least one route connecting the start and the goal junctions.

Output

Output an integer indicating the minimum possible number of personnel required.

Figure I.1. The Lowest-Cost Route for Sample Input 1

Figure I.1 shows the lowest-cost route for Sample Input 1. The arrows indicate the route and the circles painted gray are junctions requiring personnel assignment. The minimum number of required personnel is 17 in this case.

Sample Input 1

6 6
3
1
9
4
3
6
1 2
1 4
2 6
5 4
6 5
3 2

Sample Output 1

17

source: aizu

question:
Problem I
Routing a Marathon Race

As a member of the ICPC (Ibaraki Committee of Physical Competitions), you are responsible for planning the route of a marathon event held in the City of Tsukuba. A great number of runners, from beginners to experts, are expected to take part.

You have at hand a city map that lists all the street segments suited for the event and all the junctions on them. The race is to start at the junction in front of Tsukuba High, and the goal is at the junction in front of City Hall, both of which are marked on the map.

To avoid congestion and confusion of runners of divergent skills, the route should not visit the same junction twice. Consequently, although the street segments can be used in either direction, they can be included at most once in the route. As the main objective of the event is in recreation and health promotion of citizens, time records are not important and the route distance can be arbitrarily decided.

A number of personnel have to be stationed at every junction on the route. Junctions adjacent to them, i.e., junctions connected directly by a street segment to the junctions on the route, also need personnel staffing to keep casual traffic from interfering the race. The same number of personnel is required when a junction is on the route and when it is adjacent to one, but different junctions require different numbers of personnel depending on their sizes and shapes, which are also indicated on the map.

The municipal authorities are eager in reducing the costs including the personnel expense for
events of this kind. Your task is to write a program that plans a route with the minimum
possible number of personnel required and outputs that number.

Input

The input consists of a single test case representing a summary city map, formatted as follows.

$n$ $m$
$c_1$
...
$c_n$
$i_1$ $j_1$
...
$i_m$ $j_m$

The first line of a test case has two positive integers, $n$ and $m$. Here, $n$ indicates the number of junctions in the map $(2 \leq n \leq 40)$, and $m$ is the number of street segments connecting adjacent junctions. Junctions are identified by integers 1 through $n$.

Then comes $n$ lines indicating numbers of personnel required. The $k$-th line of which, an integer $c_k$ $(1 \leq c_k \leq 100)$, is the number of personnel required for the junction $k$.

The remaining $m$ lines list street segments between junctions. Each of these lines has two integers $i_k$ and $j_k$, representing a segment connecting junctions $i_k$ and $j_k$ $(i_k \ne j_k)$. There is at most one street segment connecting the same pair of junctions.

The race starts at junction 1 and the goal is at junction $n$. It is guaranteed that there is at least one route connecting the start and the goal junctions.

Output

Output an integer indicating the minimum possible number of personnel required.

![image](1.png)

Figure I.1. The Lowest-Cost Route for Sample Input 1

Figure I.1 shows the lowest-cost route for Sample Input 1. The arrows indicate the route and the circles painted gray are junctions requiring personnel assignment. The minimum number of required personnel is 17 in this case.

Sample Input 1

6 6
3
1
9
4
3
6
1 2
1 4
2 6
5 4
6 5
3 2

Sample Output 1

17

data_split: test


B. Intersecting Subtrees

problem_index: B

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
For the first sample, Li Chen's hidden permutation is $$$[2, 3, 1]$$$, and for the second, his hidden permutation is $$$[5, 3, 2, 4, 1, 6]$$$ for both cases.
In the first sample, there is a tree with three nodes in a line. On the top, is how you labeled the tree and the subtree you chose, and the bottom is how Li Chen labeled the tree and the subtree he chose:
![image](images/cf_1044_B/2.png)
In the first question, you ask Andrew to look at node $$$1$$$ in your labelling and tell you the label of it in Li Chen's labelling. Andrew responds with $$$2$$$. At this point, you know that both of your subtrees contain the same node (i.e. node $$$1$$$ according to your labeling), so you can output "C 1" and finish. However, you can also ask Andrew to look at node $$$2$$$ in Li Chen's labelling and tell you the label of it in your labelling. Andrew responds with $$$1$$$ (this step was given with the only reason — to show you how to ask questions).
For the second sample, there are two test cases. The first looks is the one from the statement:
![image](images/cf_1044_B/3.png)
We first ask "B 2", and Andrew will tell us $$$3$$$. In this case, we know $$$3$$$ is a common vertex, and moreover, any subtree with size $$$3$$$ that contains node $$$3$$$ must contain node $$$1$$$ as well, so we can output either "C 1" or "C 3" as our answer.
In the second case in the second sample, the situation looks as follows:
![image](images/cf_1044_B/4.png)
In this case, you know that the only subtree of size $$$3$$$ that doesn't contain node $$$1$$$ is subtree $$$4,5,6$$$. You ask Andrew for the label of node $$$1$$$ in Li Chen's labelling and Andrew says $$$5$$$. In this case, you know that Li Chen's subtree doesn't contain node $$$1$$$, so his subtree must be consist of the nodes $$$4,5,6$$$ (in your labelling), thus the two subtrees have no common nodes.

solutions: ["import sys\nfrom collections import deque\nt = int(sys.stdin.readline())\nfor i in range(t):\n\tn = int(sys.stdin.readline())\n\tEDGE = [list(map(int, sys.stdin.readline().split())) for i in range(n - 1)]\n\tk1 = int(sys.stdin.readline())\n\tX = list(map(int, sys.stdin.readline().split()))\n\tk2 = int(sys.stdin.readline())\n\tY = list(map(int, sys.stdin.readline().split()))\n\tprint('B', Y[0], flush=True)\n\tyans = int(input())\n\tif yans in X:\n\t\tprint('C', yans, flush=True)\n\telse:\n\t\tQUE = deque([yans])\n\t\tEDGELIST = [[] for i in range(n + 1)]\n\t\tfor (i, j) in EDGE:\n\t\t\tEDGELIST[i].append(j)\n\t\t\tEDGELIST[j].append(i)\n\t\tchecked = [0] * (n + 1)\n\t\tXLIST = [0] * (n + 1)\n\t\tfor xver in X:\n\t\t\tXLIST[xver] = 1\n\t\twhile QUE:\n\t\t\tnow = QUE.pop()\n\t\t\tchecked[now] = 1\n\t\t\tfor ver in EDGELIST[now]:\n\t\t\t\tif checked[ver] == 1:\n\t\t\t\t\tcontinue\n\t\t\t\telse:\n\t\t\t\t\tQUE.append(ver)\n\t\t\tif XLIST[now] == 1:\n\t\t\t\tbreak\n\t\tprint('A', now, flush=True)\n\t\tif int(input()) in Y:\n\t\t\tprint('C', now, flush=True)\n\t\telse:\n\t\t\tprint('C', -1, flush=True)\n", "from collections import deque\nimport sys\nt = int(input())\nfor i in range(t):\n\tn = int(input())\n\tedge = {}\n\tfor j in range(1, n + 1):\n\t\ta = set()\n\t\tedge[j] = a\n\tfor k in range(n - 1):\n\t\t(a, b) = map(int, input().split())\n\t\tedge[a].add(b)\n\t\tedge[b].add(a)\n\tk1 = int(input())\n\tx = input().split()\n\tmysubg = set()\n\tfor j in range(len(x)):\n\t\tmysubg.add(int(x[j]))\n\tk2 = int(input())\n\ty = input().split()\n\tnotmysubg = set()\n\tfor j in range(len(y)):\n\t\tnotmysubg.add(int(y[j]))\n\troot = int(x[0])\n\tprint('B ' + y[0])\n\tsys.stdout.flush()\n\tgoal = int(input())\n\td = deque([root])\n\tvisit = set()\n\tparent = {}\n\twhile len(d) > 0:\n\t\tcur = d.popleft()\n\t\tfor neigh in edge[cur]:\n\t\t\tif neigh not in visit:\n\t\t\t\tvisit.add(neigh)\n\t\t\t\td.append(neigh)\n\t\t\t\tparent[neigh] = cur\n\twhile goal != root:\n\t\tif goal in mysubg:\n\t\t\tbreak\n\t\tgoal = parent[goal]\n\tprint('A ' + str(goal))\n\tsys.stdout.flush()\n\tgoal2 = int(input())\n\tif goal2 in notmysubg:\n\t\tprint('C ' + str(goal))\n\telse:\n\t\tprint('C -1')\n", "import sys\n\ndef ask(u, t):\n\tif t == 0:\n\t\tprint('A', u)\n\telse:\n\t\tprint('B', u)\n\tsys.stdout.flush()\n\treturn int(input())\n\ndef solve():\n\tn = int(input())\n\te = [[] for _ in range(n + 1)]\n\tp = [0] * (n + 1)\n\tinA = [False] * (n + 1)\n\tfor _ in range(n - 1):\n\t\t(u, v) = map(int, input().split())\n\t\te[u].append(v)\n\t\te[v].append(u)\n\n\tdef dfs(v):\n\t\tfor u in e[v]:\n\t\t\tif p[u] == 0:\n\t\t\t\tp[u] = v\n\t\t\t\tdfs(u)\n\ta = int(input())\n\tA = list(map(int, input().split()))\n\tfor u in A:\n\t\tinA[u] = True\n\tb = int(input())\n\tB = list(map(int, input().split()))\n\tdfs(A[0])\n\tr = ask(B[0], 1)\n\twhile not inA[r]:\n\t\tr = p[r]\n\tv = ask(r, 0)\n\tprint('C', r) if v in B else print('C', -1)\n\tsys.stdout.flush()\nt = int(input())\nfor _ in range(t):\n\tsolve()\n", "import sys\nfrom math import *\nfrom random import *\n\ndef minp():\n\treturn sys.stdin.readline().strip()\n\ndef mint():\n\treturn int(minp())\n\ndef mints():\n\treturn map(int, minp().split())\n\ndef solve():\n\tn = mint()\n\te = [[] for i in range(n + 1)]\n\tp = [None] * (n + 1)\n\tmy = [False] * (n + 1)\n\tfor i in range(n - 1):\n\t\t(a, b) = mints()\n\t\te[a].append(b)\n\t\te[b].append(a)\n\n\tdef dfs(x):\n\t\tfor i in e[x]:\n\t\t\tif p[i] == None:\n\t\t\t\tp[i] = x\n\t\t\t\tdfs(i)\n\tk1 = mint()\n\tx = list(mints())\n\tfor i in x:\n\t\tmy[i] = True\n\tk2 = mint()\n\ty = list(mints())\n\tp[x[0]] = 0\n\tdfs(x[0])\n\tprint('B', y[0])\n\tsys.stdout.flush()\n\tz = mint()\n\twhile my[z] != True:\n\t\tz = p[z]\n\tprint('A', z)\n\tsys.stdout.flush()\n\tzz = mint()\n\tif zz in y:\n\t\tprint('C', z)\n\telse:\n\t\tprint('C', -1)\n\tsys.stdout.flush()\nt = mint()\nfor i in range(t):\n\tsolve()\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nfrom math import gcd, ceil\n\ndef pre(s):\n\tn = len(s)\n\tpi = [0] * n\n\tfor i in range(1, n):\n\t\tj = pi[i - 1]\n\t\twhile j and s[i] != s[j]:\n\t\t\tj = pi[j - 1]\n\t\tif s[i] == s[j]:\n\t\t\tj += 1\n\t\tpi[i] = j\n\treturn pi\n\ndef prod(a):\n\tans = 1\n\tfor each in a:\n\t\tans = ans * each\n\treturn ans\n\ndef lcm(a, b):\n\treturn a * b // gcd(a, b)\n\ndef binary(x, length=16):\n\ty = bin(x)[2:]\n\treturn y if len(y) >= length else '0' * (length - len(y)) + y\nfrom heapq import heappop, heappush\n\ndef dijkstra(n, graph, start):\n\t(dist, parents) = ([float('inf')] * n, [-1] * n)\n\tdist[start] = 0\n\tqueue = [(0, start)]\n\twhile queue:\n\t\t(path_len, v) = heappop(queue)\n\t\tif path_len == dist[v]:\n\t\t\tfor (w, edge_len) in graph[v]:\n\t\t\t\tif edge_len + path_len < dist[w]:\n\t\t\t\t\t(dist[w], parents[w]) = (edge_len + path_len, v)\n\t\t\t\t\theappush(queue, (edge_len + path_len, w))\n\treturn dist\nfor _ in range(int(input()) if True else 1):\n\tn = int(input())\n\tgraph = [[] for __ in range(n + 1)]\n\tfor i in range(n - 1):\n\t\t(x, y) = map(int, input().split())\n\t\tgraph[x] += [(y, 1)]\n\t\tgraph[y] += [(x, 1)]\n\tk1 = int(input())\n\tx = list(map(int, input().split()))\n\tk2 = int(input())\n\ty = list(map(int, input().split()))\n\tprint(f'B {y[0]}', flush=True)\n\tans = int(input())\n\tdik = dijkstra(n + 1, graph, ans)\n\tminn = 999999\n\tans = 0\n\tfor i in x:\n\t\tif dik[i] < minn:\n\t\t\tminn = dik[i]\n\t\t\tans = i\n\tprint(f'A {ans}', flush=True)\n\tb = int(input())\n\tif b in y:\n\t\tprint(f'C {ans}', flush=True)\n\telse:\n\t\tprint('C -1', flush=True)\n", "def add(child, path):\n\tcopy = path[:]\n\treturn copy + [child]\n\ndef dfs(tree, start, end, path):\n\tif start == end:\n\t\treturn path\n\tfor child in tree[start]:\n\t\tif child in path:\n\t\t\tcontinue\n\t\telse:\n\t\t\tx = dfs(tree, child, end, add(child, path))\n\t\t\tif x != None:\n\t\t\t\treturn x\n\treturn None\nt = int(input())\nfor i in range(t):\n\tn = int(input())\n\tneighbors = {}\n\tfor i in range(1, n + 1):\n\t\tneighbors[i] = []\n\tfor i in range(n - 1):\n\t\t(a, b) = map(int, input().split())\n\t\tneighbors[a].append(b)\n\t\tneighbors[b].append(a)\n\tk1 = int(input())\n\tmine = list(map(int, input().split()))\n\tk2 = int(input())\n\this = list(map(int, input().split()))\n\tprint('B', his[0])\n\tr = int(input())\n\tif r in mine:\n\t\tprint('C', r)\n\t\tcontinue\n\tway = dfs(neighbors, r, mine[0], [r])\n\tfor guy in way:\n\t\tif guy in mine:\n\t\t\tx = guy\n\t\t\tprint('A', guy)\n\t\t\tbreak\n\ts = int(input())\n\tif s in his:\n\t\tprint('C', x)\n\telse:\n\t\tprint('C', -1)\n", "from collections import defaultdict\nfrom math import log2\nfrom bisect import bisect_left\nimport os\nimport sys\nfrom io import BytesIO, IOBase\nfrom types import GeneratorType\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nsys.setrecursionlimit(10 ** 5)\n\ndef bootstrap(f, stack=[]):\n\n\tdef wrappedfunc(*args, **kwargs):\n\t\tif stack:\n\t\t\treturn f(*args, **kwargs)\n\t\telse:\n\t\t\tto = f(*args, **kwargs)\n\t\t\twhile True:\n\t\t\t\tif type(to) is GeneratorType:\n\t\t\t\t\tstack.append(to)\n\t\t\t\t\tto = next(to)\n\t\t\t\telse:\n\t\t\t\t\tstack.pop()\n\t\t\t\t\tif not stack:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tto = stack[-1].send(to)\n\t\t\treturn to\n\treturn wrappedfunc\n\n@bootstrap\ndef dfs(u, par):\n\tglobal depth\n\tfor j in adj[u]:\n\t\tif j != par:\n\t\t\tdepth[j] = depth[u] + 1\n\t\t\tyield dfs(j, u)\n\tyield\n\ndef query(s, val):\n\tprint(f'{s} {val}')\n\tsys.stdout.flush()\n\treturn int(input())\nt = int(input())\nfor _ in range(t):\n\tn = int(input())\n\tadj = [[] for i in range(n + 1)]\n\tfor i in range(n - 1):\n\t\t(u, v) = map(int, input().split())\n\t\tadj[u].append(v)\n\t\tadj[v].append(u)\n\tk1 = int(input())\n\ta = list(map(int, input().split()))\n\tk2 = int(input())\n\tb = list(map(int, input().split()))\n\tsys.stdout.flush()\n\troot = query('B', b[0])\n\tdepth = [0 for i in range(n + 1)]\n\tdfs(root, 0)\n\tm = float('inf')\n\tfor j in a:\n\t\tif depth[j] < m:\n\t\t\tm = depth[j]\n\t\t\tver = j\n\tsys.stdout.flush()\n\tval = query('A', ver)\n\tsys.stdout.flush()\n\tif val in b:\n\t\tprint(f'C {ver}')\n\telse:\n\t\tprint(f'C {-1}')\n\tsys.stdout.flush()\n"]

difficulty: HARD

source: codeforces

raw_problem:
B. Intersecting Subtrees

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

You are playing a strange game with Li Chen. You have a tree with $$$n$$$ nodes drawn on a piece of paper. All nodes are unlabeled and distinguishable. Each of you independently labeled the vertices from $$$1$$$ to $$$n$$$. Neither of you know the other's labelling of the tree.

You and Li Chen each chose a subtree (i.e., a connected subgraph) in that tree. Your subtree consists of the vertices labeled $$$x_1, x_2, \ldots, x_{k_1}$$$ in your labeling, Li Chen's subtree consists of the vertices labeled $$$y_1, y_2, \ldots, y_{k_2}$$$ in his labeling. The values of $$$x_1, x_2, \ldots, x_{k_1}$$$ and $$$y_1, y_2, \ldots, y_{k_2}$$$ are known to both of you.
   The picture shows two labelings of a possible tree: yours on the left and Li Chen's on the right. The selected trees are highlighted. There are two common nodes.
You want to determine whether your subtrees have at least one common vertex. Luckily, your friend Andrew knows both labelings of the tree. You can ask Andrew at most $$$5$$$ questions, each of which is in one of the following two forms:

 A x: Andrew will look at vertex $$$x$$$ in your labeling and tell you the number of this vertex in Li Chen's labeling.

 B y: Andrew will look at vertex $$$y$$$ in Li Chen's labeling and tell you the number of this vertex in your labeling.

Determine whether the two subtrees have at least one common vertex after asking some questions. If there is at least one common vertex, determine one of your labels for any of the common vertices.

Interaction

Each test consists of several test cases.

The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

For each testcase, your program should interact in the following format.

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 1\,000$$$) — the number of nodes in the tree.

Each of the next $$$n-1$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1\leq a_i, b_i\leq n$$$) — the edges of the tree, indicating an edge between node $$$a_i$$$ and $$$b_i$$$ according to your labeling of the nodes.

The next line contains a single integer $$$k_1$$$ ($$$1 \leq k_1 \leq n$$$) — the number of nodes in your subtree.

The next line contains $$$k_1$$$ distinct integers $$$x_1,x_2,\ldots,x_{k_1}$$$ ($$$1 \leq x_i \leq n$$$) — the indices of the nodes in your subtree, according to your labeling. It is guaranteed that these vertices form a subtree.

The next line contains a single integer $$$k_2$$$ ($$$1 \leq k_2 \leq n$$$) — the number of nodes in Li Chen's subtree.

The next line contains $$$k_2$$$ distinct integers $$$y_1, y_2, \ldots, y_{k_2}$$$ ($$$1 \leq y_i \leq n$$$) — the indices (according to Li Chen's labeling) of the nodes in Li Chen's subtree. It is guaranteed that these vertices form a subtree according to Li Chen's labelling of the tree's nodes.

Test cases will be provided one by one, so you must complete interacting with the previous test (i.e. by printing out a common node or $$$-1$$$ if there is not such node) to start receiving the next one.

You can ask the Andrew two different types of questions.

 You can print "A x" ($$$1 \leq x \leq n$$$). Andrew will look at vertex $$$x$$$ in your labeling and respond to you with the number of this vertex in Li Chen's labeling.

 You can print "B y" ($$$1 \leq y \leq n$$$). Andrew will look at vertex $$$y$$$ in Li Chen's labeling and respond to you with the number of this vertex in your labeling.

You may only ask at most $$$5$$$ questions per tree.

When you are ready to answer, print "C s", where $$$s$$$ is your label of a vertex that is common to both subtrees, or $$$-1$$$, if no such vertex exists. Printing the answer does not count as a question. Remember to flush your answer to start receiving the next test case.

After printing a question do not forget to print end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

 fflush(stdout) or cout.flush() in C++;

 System.out.flush() in Java;

 flush(output) in Pascal;

 stdout.flush() in Python;

 see documentation for other languages.

If the judge responds with $$$-1$$$, it means that you asked more queries than allowed, or asked an invalid query. Your program should immediately terminate (for example, by calling exit(0)). You will receive Wrong Answer; it means that you asked more queries than allowed, or asked an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.

Hack Format

To hack, use the following format. Note that you can only hack with one test case.

The first line should contain a single integer $$$t$$$ ($$$t=1$$$).

The second line should contain a single integer $$$n$$$ ($$$1 \leq n \leq 1\,000$$$).

The third line should contain $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1\leq p_i\leq n$$$) — a permutation of $$$1$$$ to $$$n$$$. This encodes the labels that Li Chen chose for his tree. In particular, Li Chen chose label $$$p_i$$$ for the node you labeled $$$i$$$.

Each of the next $$$n-1$$$ lines should contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1\leq a_i, b_i\leq n$$$). These edges should form a tree.

The next line should contain a single integer $$$k_1$$$ ($$$1 \leq k_1 \leq n$$$).

The next line should contain $$$k_1$$$ distinct integers $$$x_1,x_2,\ldots,x_{k_1}$$$ ($$$1 \leq x_i \leq n$$$). These vertices should form a subtree.

The next line should contain a single integer $$$k_2$$$ ($$$1 \leq k_2 \leq n$$$).

The next line should contain $$$k_2$$$ distinct integers $$$y_1, y_2, \ldots, y_{k_2}$$$ ($$$1 \leq y_i \leq n$$$). These vertices should form a subtree in Li Chen's tree according to the permutation above.

Examples

Input

1
3
1 2
2 3
1
1
1
2
2
1

Output

A 1
B 2
C 1

Input

2
6
1 2
1 3
1 4
4 5
4 6
4
1 3 4 5
3
3 5 2
3
6
1 2
1 3
1 4
4 5
4 6
3
1 2 3
3
4 1 6
5

Output

B 2
C 1
A 1
C -1

Note

For the first sample, Li Chen's hidden permutation is $$$[2, 3, 1]$$$, and for the second, his hidden permutation is $$$[5, 3, 2, 4, 1, 6]$$$ for both cases.

In the first sample, there is a tree with three nodes in a line. On the top, is how you labeled the tree and the subtree you chose, and the bottom is how Li Chen labeled the tree and the subtree he chose:

In the first question, you ask Andrew to look at node $$$1$$$ in your labelling and tell you the label of it in Li Chen's labelling. Andrew responds with $$$2$$$. At this point, you know that both of your subtrees contain the same node (i.e. node $$$1$$$ according to your labeling), so you can output "C 1" and finish. However, you can also ask Andrew to look at node $$$2$$$ in Li Chen's labelling and tell you the label of it in your labelling. Andrew responds with $$$1$$$ (this step was given with the only reason — to show you how to ask questions).

For the second sample, there are two test cases. The first looks is the one from the statement:

We first ask "B 2", and Andrew will tell us $$$3$$$. In this case, we know $$$3$$$ is a common vertex, and moreover, any subtree with size $$$3$$$ that contains node $$$3$$$ must contain node $$$1$$$ as well, so we can output either "C 1" or "C 3" as our answer.

In the second case in the second sample, the situation looks as follows:

In this case, you know that the only subtree of size $$$3$$$ that doesn't contain node $$$1$$$ is subtree $$$4,5,6$$$. You ask Andrew for the label of node $$$1$$$ in Li Chen's labelling and Andrew says $$$5$$$. In this case, you know that Li Chen's subtree doesn't contain node $$$1$$$, so his subtree must be consist of the nodes $$$4,5,6$$$ (in your labelling), thus the two subtrees have no common nodes.

question:
You are playing a strange game with Li Chen. You have a tree with $$$n$$$ nodes drawn on a piece of paper. All nodes are unlabeled and distinguishable. Each of you independently labeled the vertices from $$$1$$$ to $$$n$$$. Neither of you know the other's labelling of the tree.
You and Li Chen each chose a subtree (i.e., a connected subgraph) in that tree. Your subtree consists of the vertices labeled $$$x_1, x_2, \ldots, x_{k_1}$$$ in your labeling, Li Chen's subtree consists of the vertices labeled $$$y_1, y_2, \ldots, y_{k_2}$$$ in his labeling. The values of $$$x_1, x_2, \ldots, x_{k_1}$$$ and $$$y_1, y_2, \ldots, y_{k_2}$$$ are known to both of you.
 ![image](1.png)  The picture shows two labelings of a possible tree: yours on the left and Li Chen's on the right. The selected trees are highlighted. There are two common nodes. You want to determine whether your subtrees have at least one common vertex. Luckily, your friend Andrew knows both labelings of the tree. You can ask Andrew at most $$$5$$$ questions, each of which is in one of the following two forms:
 -  A x: Andrew will look at vertex $$$x$$$ in your labeling and tell you the number of this vertex in Li Chen's labeling. -  B y: Andrew will look at vertex $$$y$$$ in Li Chen's labeling and tell you the number of this vertex in your labeling. Determine whether the two subtrees have at least one common vertex after asking some questions. If there is at least one common vertex, determine one of your labels for any of the common vertices.

Interaction
Each test consists of several test cases.
The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.
For each testcase, your program should interact in the following format.
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 1\,000$$$) — the number of nodes in the tree.
Each of the next $$$n-1$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1\leq a_i, b_i\leq n$$$) — the edges of the tree, indicating an edge between node $$$a_i$$$ and $$$b_i$$$ according to your labeling of the nodes.
The next line contains a single integer $$$k_1$$$ ($$$1 \leq k_1 \leq n$$$) — the number of nodes in your subtree.
The next line contains $$$k_1$$$ distinct integers $$$x_1,x_2,\ldots,x_{k_1}$$$ ($$$1 \leq x_i \leq n$$$) — the indices of the nodes in your subtree, according to your labeling. It is guaranteed that these vertices form a subtree.
The next line contains a single integer $$$k_2$$$ ($$$1 \leq k_2 \leq n$$$) — the number of nodes in Li Chen's subtree.
The next line contains $$$k_2$$$ distinct integers $$$y_1, y_2, \ldots, y_{k_2}$$$ ($$$1 \leq y_i \leq n$$$) — the indices (according to Li Chen's labeling) of the nodes in Li Chen's subtree. It is guaranteed that these vertices form a subtree according to Li Chen's labelling of the tree's nodes.
Test cases will be provided one by one, so you must complete interacting with the previous test (i.e. by printing out a common node or $$$-1$$$ if there is not such node) to start receiving the next one.
You can ask the Andrew two different types of questions.
 -  You can print "A x" ($$$1 \leq x \leq n$$$). Andrew will look at vertex $$$x$$$ in your labeling and respond to you with the number of this vertex in Li Chen's labeling. -  You can print "B y" ($$$1 \leq y \leq n$$$). Andrew will look at vertex $$$y$$$ in Li Chen's labeling and respond to you with the number of this vertex in your labeling. You may only ask at most $$$5$$$ questions per tree.
When you are ready to answer, print "C s", where $$$s$$$ is your label of a vertex that is common to both subtrees, or $$$-1$$$, if no such vertex exists. Printing the answer does not count as a question. Remember to flush your answer to start receiving the next test case.
After printing a question do not forget to print end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
 -  fflush(stdout) or cout.flush() in C++; -  System.out.flush() in Java; -  flush(output) in Pascal; -  stdout.flush() in Python; -  see documentation for other languages. If the judge responds with $$$-1$$$, it means that you asked more queries than allowed, or asked an invalid query. Your program should immediately terminate (for example, by calling exit(0)). You will receive Wrong Answer; it means that you asked more queries than allowed, or asked an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.
Hack Format
To hack, use the following format. Note that you can only hack with one test case.
The first line should contain a single integer $$$t$$$ ($$$t=1$$$).
The second line should contain a single integer $$$n$$$ ($$$1 \leq n \leq 1\,000$$$).
The third line should contain $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1\leq p_i\leq n$$$) — a permutation of $$$1$$$ to $$$n$$$. This encodes the labels that Li Chen chose for his tree. In particular, Li Chen chose label $$$p_i$$$ for the node you labeled $$$i$$$.
Each of the next $$$n-1$$$ lines should contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1\leq a_i, b_i\leq n$$$). These edges should form a tree.
The next line should contain a single integer $$$k_1$$$ ($$$1 \leq k_1 \leq n$$$).
The next line should contain $$$k_1$$$ distinct integers $$$x_1,x_2,\ldots,x_{k_1}$$$ ($$$1 \leq x_i \leq n$$$). These vertices should form a subtree.
The next line should contain a single integer $$$k_2$$$ ($$$1 \leq k_2 \leq n$$$).
The next line should contain $$$k_2$$$ distinct integers $$$y_1, y_2, \ldots, y_{k_2}$$$ ($$$1 \leq y_i \leq n$$$). These vertices should form a subtree in Li Chen's tree according to the permutation above.

Examples
Input
1
3
1 2
2 3
1
1
1
2
2
1

Output
A 1
B 2
C 1

Input
2
6
1 2
1 3
1 4
4 5
4 6
4
1 3 4 5
3
3 5 2
3
6
1 2
1 3
1 4
4 5
4 6
3
1 2 3
3
4 1 6
5

Output
B 2
C 1
A 1
C -1

Note
For the first sample, Li Chen's hidden permutation is $$$[2, 3, 1]$$$, and for the second, his hidden permutation is $$$[5, 3, 2, 4, 1, 6]$$$ for both cases.
In the first sample, there is a tree with three nodes in a line. On the top, is how you labeled the tree and the subtree you chose, and the bottom is how Li Chen labeled the tree and the subtree he chose:
 ![image](2.png) In the first question, you ask Andrew to look at node $$$1$$$ in your labelling and tell you the label of it in Li Chen's labelling. Andrew responds with $$$2$$$. At this point, you know that both of your subtrees contain the same node (i.e. node $$$1$$$ according to your labeling), so you can output "C 1" and finish. However, you can also ask Andrew to look at node $$$2$$$ in Li Chen's labelling and tell you the label of it in your labelling. Andrew responds with $$$1$$$ (this step was given with the only reason — to show you how to ask questions).
For the second sample, there are two test cases. The first looks is the one from the statement:
 ![image](3.png) We first ask "B 2", and Andrew will tell us $$$3$$$. In this case, we know $$$3$$$ is a common vertex, and moreover, any subtree with size $$$3$$$ that contains node $$$3$$$ must contain node $$$1$$$ as well, so we can output either "C 1" or "C 3" as our answer.
In the second case in the second sample, the situation looks as follows:
 ![image](4.png) In this case, you know that the only subtree of size $$$3$$$ that doesn't contain node $$$1$$$ is subtree $$$4,5,6$$$. You ask Andrew for the label of node $$$1$$$ in Li Chen's labelling and Andrew says $$$5$$$. In this case, you know that Li Chen's subtree doesn't contain node $$$1$$$, so his subtree must be consist of the nodes $$$4,5,6$$$ (in your labelling), thus the two subtrees have no common nodes.

raw_tags: ['trees', 'dfs and similar', 'interactive']

image_tags: Tree Tree Tree Tree

data_split: test