Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import decimal
from itertools import permutations


decimal.getcontext().prec = 16

def distance(a, b):
  return decimal.Decimal(pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2)).sqrt()


N = int(input())

P = [None] * N
for i in range(N):
  P[i] = tuple(map(int, input().split()))

total = decimal.Decimal(0)
count = 0
for points in permutations(P, len(P)):
  it = iter(points)
  last = next(it)
  for p in it:
    total += distance(p, last)
    last = p
  count += 1

print(total / count)


### FIXED CODE ###

import decimal
import math
from itertools import permutations

decimal.getcontext().prec = 16

cache = {}


def distance(a, b):
  return math.sqrt(pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2))


N = int(input())

P = [None] * N
for i in range(N):
  P[i] = tuple(map(int, input().split()))

total = 0
count = 0
for points in permutations(P, len(P)):
  it = iter(points)
  last = next(it)
  for p in it:
    total += distance(p, last)
    last = p
  count += 1

print(total / count)
### BUGGY CODE ###

def segfunc(x,y):
  return x|y
ide_ele=set()
class SegTree():
  def __init__(self,init_val,segfunc,ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]={init_val[i]}
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def update(self,k,x):
    k+=self.num
    self.tree[k]=x
    while k>1:
      self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
      k>>=1
  def query(self,l,r):
    res=self.ide_ele
    l+=self.num
    r+=self.num
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
n,q=map(int,input().split())
c=list(map(int,input().split()))
st=SegTree(c,segfunc,ide_ele)
for _ in range(q):
  l,r=map(int,input().split())
  print(len(st.query(l-1,r)))

### FIXED CODE ###

def segfunc(x,y):
  return x+y
ide_ele=0
class SegTree():
  def __init__(self,init_val,segfunc,ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def update(self,k,x):
    k+=self.num
    self.tree[k]=x
    while k>1:
      self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
      k>>=1
  def query(self,l,r):
    res=self.ide_ele
    l+=self.num
    r+=self.num
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
n,q=map(int,input().split())
c=list(map(int,input().split()))
st=SegTree([0]*n,segfunc,ide_ele)
lr=[[]for _ in range(n+1)]
for i in range(q):
  l,r=map(int,input().split())
  lr[r]+=[(l,i)]
d={}
for i in range(n):
  if not d.get(c[i]):d[c[i]]=[i]
  else:d[c[i]]+=[i]
for i in d:
  st.update(d[i][-1],1)
ans=[0]*q
r=n
while r>0:
  if lr[r]:
    l,i=lr[r].pop()
    ans[i]=st.query(l-1,r)
  while not lr[r] and r>0:
    if d[c[r-1]]:st.update(d[c[r-1]].pop(),0)
    if d[c[r-1]]:st.update(d[c[r-1]][-1],1)
    r-=1
for i in ans:print(i)
### BUGGY CODE ###

K = int(input())
A = list(map(int, input().split()))
A.reverse()
A.append(1)
prev = set()
if A[0] == 2:
  prev.add(2)

for i in range(K):
  a = A[i]
  an = A[i+1]
  s = set()
  for n in prev:
    if n+a <= an:
      continue
    for x in range(((n+an-1)//an)*an, n+a, an):
      s.add(x)
  prev = s

if len(prev) > 0:
  print(min(prev), max(prev))
else:
  print('-1')

### FIXED CODE ###

K = int(input())
A = list(map(int, input().split()))
A.reverse()
A.append(1)
ansmin = 2
ansmax = 2
for a in A:
  tmin = ((ansmin+a-1)//a)*a
  tmax = (ansmax//a)*a
  if tmin > tmax:
    print('-1')
    exit()
  ansmin = tmin
  ansmax = tmax + a - 1
print(ansmin, ansmax)
### BUGGY CODE ###

N    = int(input())
order=list(map(int,input().split()))
output=[]


for i in range(N):
    output.append((order.index(i+1))+1)
print(' '.join(map(str,output)))

### FIXED CODE ###


N    = int(input())
order=list(map(int,input().split()))
output=[0]*N

for i in range(N):
    output[order[i]-1]=i+1

print(' '.join(map(str,output)))
### BUGGY CODE ###

from math import ceil, floor

# dp[a_i番まで見た。a_iを含む][a_i（を含む）までにいくつ採用しているか][i - 1を使ったかどうか] bool


def main():
    n = int(input())
    A = [0] + list(map(int, input().split()))
    dp = {}
    dp[(0, 0)] = 0
    dp[(1, 1)] = A[1]
    dp[(1, 0)] = 0
    for i in range(2, n + 1):
        for j in range(max(floor(n/2) - ceil((n-i)/2), 0), floor(n/2) + 1):
            # a_iを採用する場合
            if (i, j) in dp:
                dp[(i, j)] = max(dp[(i, j)], A[i] + dp[(i - 2, j - 1)]
                                 ) if (i - 2, j - 1) in dp else dp[(i, j)]
            else:
                dp[(i, j)] = A[i] + dp[(i - 2, j - 1)] if (i -
                                                           2, j - 1) in dp else float("inf")*-1
            # a_iを採用しない場合
            if (i - 1, j) in dp:
                dp[(i, j)] = max(dp[(i - 1, j)], dp[(i, j)])

    print(dp[(n, floor(n/2))])
    return


"""
7
0を取ったところ
#######
#0#0#0#
0#0#0##
0#0##0#
0#0###0
##0#0#0

4
0#0#
#0#0
0##0
"""
if __name__ == "__main__":
    main()


### FIXED CODE ###

from math import ceil, floor

# dp[a_i番まで見た。a_iを含む][a_i（を含む）までにいくつ採用しているか][i - 1を使ったかどうか] bool
memo = {}


def dp(i, j):
    if (i, j) in memo:
        return memo[(i, j)]
    else:
        return float("inf")*-1


def main():
    n = int(input())
    A = [0] + list(map(int, input().split()))
    memo[(0, 0)] = 0
    memo[(1, 1)] = A[1]
    memo[(1, 0)] = 0
    for i in range(2, n + 1):
        for j in range(max(floor(n/2) - ceil((n-i)/2) - 1, 0), floor(i/2) + 5):
            # a_iを採用する場合
            if (i, j) in memo:
                memo[(i, j)] = max(
                    [dp(i, j), A[i] + dp(i - 2, j - 1), A[i] + dp(i - 3, j - 1)])
            else:
                memo[(i, j)] = max(A[i] + dp(i - 2, j - 1),
                                   A[i] + dp(i - 3, j - 1))
            # a_iを採用しない場合
            if (i - 1, j) in memo:
                memo[(i, j)] = max(dp(i - 1, j), dp(i, j))

    print(dp(n, floor(n/2)))
    return
if __name__ == "__main__":
    main()
### BUGGY CODE ###

num_n = input()
N = map(int, raw_input().split())
num_m = input()
M = map(int, raw_input().split())
  
def solve(i, m):
   if m == 0:
      return True
   if i >= num_n or m > sum(M):
      return False
   res = solve(i + 1, m) or solve(i + 1,m - N[i])
   return res
   
for m in M:
   if solve(0, m):
      print "yes"
   else:
      print "no"

### FIXED CODE ###

_ = int(input())
hoge = [int(x) for x in input().split()]
_ = int(input())

def exSearch(i, m):
    if m == 0:
        return True
    if i >= len(hoge) or m > sum(hoge):
        return False
    res = exSearch(i+1, m) or exSearch(i+1, m-hoge[i])
    return res

if __name__ == '__main__':
    
    for val in (int(x) for x in input().split()):
        if exSearch(0, val):
            print ('yes')
        else:
            print ('no')
### BUGGY CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

# N = int(input())
N, K = map(int, input().split())
D = [int(x) for x in input().split()]
# S = input()

ans_list = set()
for l in range(N + 1):
    if l > K:
        break

    for r in range(N - l + 1):
        if l + r > K:
            break

        l_list = sorted(D[0 : l])
        r_list = sorted(D[N - r : N])

        for discard_l in range(K - (l + r) + 1):
            for discard_r in range(K - (l + r + discard_l) + 1):
                value = sum(l_list[discard_l:])
                value += sum(r_list[discard_r:])

                ans_list.add(value)
        
print(sorted(ans_list, reverse=True)[0])


### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

# N = int(input())
N, K = map(int, input().split())
D = [int(x) for x in input().split()]
# S = input()

ans = 0
for l in range(N + 1):
    if l > K:
        break

    for r in range(N - l + 1):
        if l + r > K:
            break

        value_list = D[0 : l] + D[N - r : N]
        value_list.sort()
        
        for i in range(K - (l + r) + 1):
            ans = max(ans, sum(value_list[i:]))
        
print(ans)
### BUGGY CODE ###

a = int(input())
s = list(map(int,input().split()))
num = 1
for i in range(a):
    num *=s[i]
    if s[i] ==0:
      print(0)
      exit()    
if num > (10**18):
    print(-1)
    exit()
else:
    print(num)

### FIXED CODE ###

a = int(input())
s =list(map(int,input().split()))
mod = 10 **18
ans = 1
if 0 in s:
    print(0)
    exit()
for i in s:
    ans = ans *i
    if ans > 1e18:
      print(-1)
      exit()
print(ans)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
cnt = 0
for i in range(n):
    if all(p[i]<=p[j] for j in range(i+1)):
        cnt += 1

print(cnt)

### FIXED CODE ###

N = int(input())
p = list(map(int, input().split()))

cnt = 0
m = 10**6
for i in p:
    if i < m:
        m = i
        cnt += 1
print(cnt)
### BUGGY CODE ###


def next7(s):
    return s * 10 + 7


def submit():
    k = int(input())

    if k % 2 == 0:
        print(-1)
        return
    if k == 5:
        print(-1)
        return

    s = 7
    ans = 1
    while s % k:
        s = next7(s)
        ans += 1

    print(ans)


submit()    

### FIXED CODE ###


def submit():
    k = int(input())

    if k % 2 == 0:
        print(-1)
        return
    if k % 5 == 0:
        print(-1)
        return

    d = {}
    for t in [1, 3, 7, 9]:
        d[t] = {}
        for i in range(10):
            d[t][t * i % 10] = i
    
    td = k % 10
    curr = 0
    count = 0
    while count == 0 or curr != 0:
        diff = 7 - (curr % 10)
        if diff != 0:
            if diff < 0:
                diff += 10
            coef = d[td][diff]
            curr += coef * k
        curr //= 10
        count += 1

    print(count)
    
submit()
### BUGGY CODE ###

import functools
import operator

n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
total_act = 0
total_act2 = 1
total = []
for i in range(n + 1):
    if str(i) not in a:
        total_act3 = total_act2 + total_act
        total_act2 = total_act
        total_act = total_act3
    else:
        total.append(total_act)
        total_act = 0
        total_act2 = 1
total.append(total_act)
result = functools.reduce(operator.mul, total)
print(result % 1000000007)


### FIXED CODE ###

n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
b = []
c = []
total_act = 0
total_act2 = 1
total = 1
if m == 0:
    for i in range(n + 1):
        if str(i) in a:
            total *= total_act
            total_act = 0
            total_act2 = 1
        else:
            total_act3 = total_act2 + total_act
            total_act2 = total_act
            total_act = total_act3
    total *= total_act
    print(total % 1000000007)
else:
    b.append(int(a[0]))
    for i in range(len(a) - 1):
        b.append(int(a[i + 1]) - int(a[i]) - 1)
        if int(a[i + 1]) - int(a[i]) - 1 == 0:
            print(0)
            exit()
    b.append(n - int(a[-1]))

    for i in range(max(b)):
        total_act3 = total_act2 + total_act
        total_act2 = total_act
        total_act = total_act3
        c.append(total_act)

    for i in b:
        total *= c[i - 1]
    print(total % 1000000007)
### BUGGY CODE ###

import collections

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A = collections.Counter(ZZ())
    e = collections.defaultdict(list)
    l = [False] * (10 ** 6 + 5)

    def yakusu(num):
        ret = []
        for i in range(1, num + 1):
            if i * i > num: break
            if num%i != 0: continue
            ret.append(i)
            if i != num//i: ret.append(num//i)
        return ret

    if 1 in A.keys():
        if A[1] == 1: print(1)
        elif A[1] >= 2: print(0)
        return

    ans = 0
    for n in A.keys():
        l[n] = True
        e[n] = yakusu(n)

    for n in A.keys():
        if A[n] >= 2: continue
        for p in e[n]:
            if p in {1, n}: continue
            if l[p]: break
        else: ans += 1
    print(ans)

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A = sorted(ZZ())
    cA = collections.Counter(A)
    MAX_A = 10 ** 6
    is_ok = [True] * (MAX_A + 1)

    if 1 in cA.keys():
        if cA[1] == 1: print(1)
        elif cA[1] >= 2: print(0)
        return

    for a in cA.keys():
        if not is_ok[a]: continue
        if cA[a] >= 2: is_ok[a] = False
        for i in range(2, MAX_A + 1):
            if a * i > MAX_A: break
            is_ok[a * i] = False

    ans = 0
    for a in cA.keys():
        if is_ok[a]: ans += 1

    print(ans)

    return

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')] * 10 ** 5

dp[0] = 0
for i in range(1, N):
  tmp = i
  if tmp > K:
    tmp = K
  for j in range(1,tmp + 1):
      dp[i] = min(dp[i], dp[i - j] + abs(h[i - j] - h[i]))

print(dp[N-1])


### FIXED CODE ###

N,K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')] * 10 ** 5

dp[0] = 0
for i in range(1, N):
  tmp = i
  if tmp > K:
    tmp = K
  for j in range(1,tmp + 1):
      dp[i] = min(dp[i], dp[i - j] + abs(h[i - j] - h[i]))

print(dp[N-1])
### BUGGY CODE ###

# -*-coding: utf-8 -*-
import numpy as np

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    np_A = np.array(A)
    for i in range(M):
        num = np_A.argmax()
        np_A[num] //= 2
    print(sum(np_A))

if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*-coding: utf-8 -*-
import heapq
def main():
    N, M = map(int, input().split())
    A = list(map(lambda x: int(x)*(-1), input().split()))
    heapq.heapify(A)

    for _ in range(M):
        tmp_min = heapq.heappop(A)
        heapq.heappush(A, (-1)*(-tmp_min//2))
    
    print(-sum(A))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def inpl():
    return list(map(int, input().split()))


H, N = inpl()
AB = [inpl() for i in range(N)]

# print(AB)
ans = [float("inf") for _ in range(H + 1)]
ans[0] = 0

for a, b in AB:
    # print(a, b)
    for i in range(H):
        ni = min(i + a, H)
        # print(i)
        ans[ni] = min(ans[ni], ans[i] + b)

print(ans[H])


### FIXED CODE ###

import sys
import functools


def inpl():
    return list(map(int, input().split()))


@functools.lru_cache(maxsize=None)
def solve(h):
    if h <= 0:
        return 0

    ret_val = float("inf")
    for a, b in AB:
        val = b + solve(h - a)
        if val < ret_val:
            ret_val = val
        else:
            break
    return ret_val


sys.setrecursionlimit(100000)

H, N = inpl()
AB = [inpl() for i in range(N)]
AB.sort(key=lambda ab: (ab[0] / ab[1], -ab[0]), reverse=True)
# print(AB)
print(solve(H))
### BUGGY CODE ###

s=input()
n=len(s)
sn=[0]*n
x=pow(10,n-1)
for i in range(n):
    sn[i]=int(s[i])*x
    x=x//10
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-sn[i-1]
    t[i]%=2019
t.sort()
t2=sorted(list(set(t)))
tcnt=[0]*len(t2)
f=0
for i in range(n+1):
    if t2[f]==t[i]:
        tcnt[f]+=1
    else:
        f+=1
        tcnt[f]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)


### FIXED CODE ###

s=input()
n=len(s)
s_int=[0]*n
x=(pow(10,n-1))%2019
for i in range(n):
    s_int[i]=(int(s[i])*x)%2019
    x=(x*202)%2019
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-s_int[i-1]
    t[i]%=2019
t.sort()
t_set=sorted(list(set(t)))
tcnt=[0]*len(t_set)
num=0
for i in range(n+1):
    if t_set[num]==t[i]:
        tcnt[num]+=1
    else:
        num+=1
        tcnt[num]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)
### BUGGY CODE ###

while 1:
    try:
        s1 = raw_input()
        s2 = raw_input()
        if len(s1) < len(s2): s1,s2 = s2,s1
        l = sum(min(s1.count(i), s2.count(i)) for i in set(list(s1)) & set(list(s2)))
        if l == 0: print 0; continue
        f = False
        for i in range(l,0,-1):
            for j in range(len(s2)-i+1):
                if s2[j:j+i] in s1:
                    f = True
                    print i
                    break
            if f: break
    except:
        break

### FIXED CODE ###

while 1:
    try:
        s1 = raw_input()
        s2 = raw_input()
        if len(s1) < len(s2): s1,s2 = s2,s1
        l = sum(min(s1.count(i), s2.count(i)) for i in set(list(s1)) & set(list(s2)))
        if l == 0: print 0; continue
        ans = 0
        for i in range(len(s2)):
            if len(s2) - i <= ans: break
            for j in range(ans+1, min(l + 1,len(s2)-i+1)):
                if s2[i:i+j] in s1:
                    ans = j
                else: break
        print ans
    except:
        break
### BUGGY CODE ###

class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)

N, Q = map(int, input().split())
Cs = [0] + list(map(int, input().split()))

Qs = []
for i in range(Q):
  l,r = map(int, input().split())
  Qs.append((i,l,r))
  
Qs.sort(key=lambda x:x[2])

ans = [-1]*Q
dic = {}
b = 1
bt = BIT(N)

for i,l,r in Qs:
  for j in range(b,r+1):
    if Cs[j] in dic:
      bt.add(dic[Cs[j]],-1)
    dic[Cs[j]] = j
    bt.add(j, 1)
  ans[i] = bt.get(l-1,r)
  
for i in range(Q):
  print(ans[i])

### FIXED CODE ###

from sys import stdin
input = stdin.readline
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n, q = map(int, input().split())
tmp = list(map(int, input().split()))
color = [-1]
for v in tmp:
    color.append(v)
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 1
bit = Bit(n)
for l, r, i in qry:
    if last_update_idx < r+1:
        st = set()
        for j in range(last_update_idx, r+1):
            if not color[j] in st and color[j] in dic:
                bit.add(dic[color[j]], -1)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            bit.add(dic[v], 1)
        last_update_idx = r+1
    ans[i] = bit.sum(r) - bit.sum(l)
for v in ans:
    print(v)
### BUGGY CODE ###

N = int(input())

for i in range(1,N+1):
  ans = 0
  if i < 6:
    print(ans)
  else:
    for a in range(2,int((2*i)**0.5+1)):
      for b in range(a,int((2*i-a**2)**0.5+1)):
        for c in range(b,int((2*i-a**2-b**2)**0.5+1)):
          #print(a,b,c)
          if a**2 + b**2 + c**2 > 2*i:
            ans = 0
          if a**2 + b**2 + c**2 == 2*i:
            if max(a,b,c) < a+b+c-max(a,b,c):
              if len({a,b,c}) == 1:
                ans = 1
              elif len({a,b,c}) == 2:
                ans = 3
              else:
                ans = 6
              #print(a,b,c)
    print(ans)



### FIXED CODE ###

import numpy as np

N = int(input())

#print(1e+5)
ans = np.zeros(int(1e+5),dtype = int)
for x in range(1,int(N**0.5+1)):
  for y in range(x,int((N-x**2)**0.5+1)):
    for z in range(y,int((N-x**2-y**2)**0.5+1)):
      n = x**2 + y**2 + z**2 +x*y+y*z+z*x
      num = len({x,y,z})
      if num == 1:
        ans[n] += 1
      elif num == 2:
        ans[n] += 3
      elif num == 3:
        ans[n] += 6

for i in range(1,N+1):
  print(ans[i])
### BUGGY CODE ###

n = int(input())

a = [int(input()) for i in range(n)]

paper = []

for number in a:
    if not number in paper:
        paper.append(number)
    
    else:
        paper.remove(number)

print(len(paper))
        

### FIXED CODE ###

n = int(input())

a = [int(input()) for i in range(n)]

a = sorted(a)


temp = a[0]
c = 0

cnts = [0]*n

for i in a:
    if temp == i:
        cnts[c] += 1
    
    else:
        temp = i
        c += 1
        cnts[c] += 1

ans = 0

for i in cnts:
    if i == 0:
        break

    if i%2 == 1:
        ans += 1

print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
info = [list(map(int, input().split())) for _ in range(q)]
ans = []
for l, r in info:
    ans.append(s[l-1:r].count('AC'))

for i in range(q):
    print(ans[i])

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
info = [list(map(int, input().split())) for _ in range(q)]
all = s.count('AC')
ans = []
lt = [all]
rt = [all]
# for i in range(n):
#     lt.append(all - s[i:].count('AC'))
#     rt.append(all - s[:n-i].count('AC'))
for i in range(1, n):
    if s[i-1] == 'A' and s[i] == 'C':
        lt.append(lt[i-1] - 1)
    else:
        lt.append(lt[i-1])
    if s[n-i-1] == 'A' and s[n-i] == 'C':
        rt.append(rt[i-1] - 1)
    else:
        rt.append(rt[i-1])

rt.reverse()
# print(lt)
# print(rt)
# print(rt)
for l, r in info:
    ans.append(lt[l-1] + rt[r-1] - all)

for i in range(q):
    print(ans[i])
### BUGGY CODE ###

n,w=map(int,input().split())
ans=[0]*(w+1)
for i in range(n):
    e,v=map(int,input().split())
    for j in range(w,-1,-1):
        if j+e<=w:
            ans[j+e]=max(ans[j]+v,ans[j+e])
print(max(ans))

### FIXED CODE ###

n,w=map(int,input().split())
ans=[0]*(w+1)
for i in range(n):
    e,v=map(int,input().split())
    for j in range(w,-1,-1):
        if j+e<=w:
            ans[j+e]=max(ans[j]+v,ans[j+e])
print(max(ans))
### BUGGY CODE ###

# 頂点を3回ずつに持つ (x歩目の着地）
# 最短路

import sys
from scipy.sparse import *
input = sys.stdin.readline
N,M = map(int,input().split())
U,V = [],[]
for _ in range(M):
  u,v = map(int,input().split())
  U.append(u)
  V.append(v)
S,T = map(int,input().split())


# ken
rows = [3*u for u in U]
cols = [3*v+1 for v in V]
# ken
rows += [3*u+1 for u in U]
cols += [3*v+2 for v in V]
# pa
rows += [3*u+2 for u in U]
cols += [3*v for v in V]

graph = csr_matrix(([1] * len(rows), (rows, cols)), (3*N+3, 3*N+3))
dist = csgraph.dijkstra(graph, indices = 3*S)

# 着地地点に制限
dist = dist[::3]

answer = -1 if dist[T] > 3*N else int(dist[T]//3)
print(answer)

### FIXED CODE ###

# 頂点を3回ずつに持つ (x歩目の着地）
# 最短路

import sys
input = sys.stdin.readline
N,M = map(int,input().split())
if M == 0:
  print(-1)
  exit()
edge = [[] for _ in range(N+1)]
for _ in range(M):
  u,v = map(int,input().split())
  edge[u].append(v)
S,T = map(int,input().split())

INF = 10 ** 9
dist = [[INF,INF,INF] for _ in range(N+1)]

d = 0
q = [S]
while q:
  d += 1
  r = d % 3
  qq = []
  for u in q:
    for v in edge[u]:
      if dist[v][r] == INF:
        dist[v][r] = d
        qq.append(v)
  q = qq

d = dist[T][0]
answer = -1 if d == INF else d // 3
print(answer)
### BUGGY CODE ###

n = int(input())
C = list(map(int, input().split()))

mod = 10**9 + 7

if n == 1:
    ans = 2 * C[0]
    ans %= mod
    print(ans)
    exit()


ans = 0
pattern = 2 ** (n-1)
C.sort(reverse=True)
for c in C:
    ans += (c * pattern) % mod
    pattern += 2 ** (n-2)
    pattern %= mod
    ans %= mod

print(ans*(2**n) % mod)

### FIXED CODE ###

n = int(input())
C = list(map(int, input().split()))

mod = 10**9 + 7

if n == 1:
    ans = 2 * C[0]
    ans %= mod
    print(ans)
    exit()


ans = 0
pattern = 2 ** (n-1) % mod
d = 2 ** (n-2) % mod
C.sort(reverse=True)
for c in C:
    ans += (c * pattern) % mod
    pattern += d
    pattern %= mod
    ans %= mod

print(ans*(2**n) % mod)