# Task
 You are given a string consisting of `"D", "P" and "C"`. A positive integer N is called DPC of this string if it satisfies the following properties: 
 
 ```
 For each i = 1, 2, ... , size of the string:

 If i-th character is "D", then N can be divided by i
 If i-th character is "P", then N and i should be relatively prime
 If i-th character is "C", then N should neither be divided by i 
                           nor be relatively prime with i```

Your task is to find the smallest DPC of a given string, or return `-1` if there is no such. The result is guaranteed to be `<= 10^9`.

# Example
 For `s = "DDPDD"`, the result should be `20`.
 
 `"DDPDD"` means `N` should `divided by 1,2,4,5`, and `N,3` should be relatively prime. The smallest N should be `20`.

# Input/Output


 - `[input]` string `s`

  The given string


 - `[output]` an integer

  The smallest DPC of `s` or `-1` if it doesn't exist.

Difficulty: introductory

Starter code:

def DPC_sequence(s):
	

Solutions:
from fractions import gcd

def DPC_sequence(s):
    n=1
    for i,c in enumerate(s,1):
        if c=='D':
            n=(n*i)//gcd(n,i)
        elif c=='P':
            if gcd(n,i)!=1: return -1
        elif c=='C':
            if gcd(n,i) in (1,i): return -1
    return n


from fractions import gcd

def DPC_sequence(s):
    n = 1
    for i, c in enumerate(s, 1):
        if c == 'D': n = n * i // gcd(n, i)
    for i, c in enumerate(s, 1):
        g = gcd(n, i)
        if c == 'P' and 1 < g: return -1
        if c == 'C' and not 1 < g < i: return -1
    return n

from fractions   import gcd
from collections import defaultdict
from functools   import reduce

def lcm(a,b):        return int(a*b/gcd(a,b))
def full_lcm(*args): return reduce(lcm, args)

def DPC_sequence(s):
    DPC_dct = defaultdict(set)
    for i,c in enumerate(s,1): DPC_dct[c].add(i)
    n = full_lcm(*DPC_dct['D'])
    return  -1 if any( gcd(n, x) in [1, x] for x in DPC_dct['C']) or any( gcd(n, x) != 1 for x in DPC_dct['P']) else n


from math import gcd
from functools import reduce

def DPC_sequence(s):
    def lcm(a, b):
        return a*b // gcd(a, b)
    
    d, p, c = [], [], []
    for i in range(len(s)):
        if s[i] == "D": 
            d.append(i+1)
        elif s[i] == "P":
            p.append(i+1)
        else:
            c.append(i+1)
    
    if not d:
        return -1
    lcm_d = reduce(lambda i, j: lcm(i, j), d)
    for i in p:
        if gcd(lcm_d, i) != 1:
            return -1
    for i in c:
        if lcm_d % i == 0 or gcd(lcm_d, i) == 1:
            return -1
    return lcm_d


from math import gcd

try:
    from math import prod
except ImportError:
    def prod(l, p=1):
        for n in l: p *= n
        return p

max_n = 1000000000

def DPC_sequence(s):
    if s[0] == 'C':
        return -1
    primes = list(find_primes(len(s)))
    pf = []
    for p in primes:
        if s[p-1] == 'C':
            return -1
        if s[p-1] == 'D':
            pf.append(p)
    #print(pf)
    for p in pf:
        for i in range(2*p-1, len(s), p):
            if s[i] == 'P':
                return -1
    base = prod(pf)
    nmax = min(prod(primes), max_n)
    #print(base, nmax)
    for n in range(base, nmax, base):
        if test(s, n):
            return n
    return -1

def test(s, n):
    for k in range(2, len(s)+1):
        c = s[k-1]
        if c == 'D':
            if n % k != 0: return False
        else:
            if (gcd(n, k) == 1) != (c == 'P'): return False
    return True

def find_primes(n):
    if n < 2: return
    yield 2
    s = list(range(1, n+1, 2))
    mroot = int(n ** 0.5)
    half = (n+1) // 2
    i = 1
    m = 3
    while m <= mroot:
        if s[i]:
            yield s[i]
            j = m*m // 2
            while j < half:
                s[j] = 0
                j += m
        i += 1
        m += 2
    for x in s[i:]:
        if x:
            yield x


from math import gcd
def DPC_sequence(s):
    r=1
    pset=set()
    for i,c in enumerate(s):
        x=i+1
        if c=='D':
            if r%x==0:
                continue
            y=x//gcd(r,x)
            if y in pset:
                return-1
            r*=y
        elif c=='P':
            if r%x==0 or gcd(r,x)>1:
                return -1
            pset.add(x)
        else:
            if r%x==0 or gcd(r,x)==1:
                return -1
    return r

from fractions import gcd

def DPC_sequence(s):
    res = 1
    
    for i, c in enumerate(s, 1):
        if c == 'D':
            res *= i // gcd(i, res)
            
    def check_DPC_at(i, c):
        if c == 'D':
            return gcd(i, res) == i
        elif c == 'C':
            return gcd(i, res) in range(2, i)
        elif c == 'P':
            return gcd(i, res) == 1
            
    return res if all(check_DPC_at(*e) for e in enumerate(s, 1)) else -1


from math import gcd
from copy import copy


def DPC_sequence(s):
    d = [x for x, y in enumerate(s, 1) if y == 'D']
    p = [x for x, y in enumerate(s, 1) if y == 'P']
    c = [x for x, y in enumerate(s, 1) if y == 'C']
    D = lcm(d) if len(d) > 1 else d[0]
    return D if all(gcd(D, i) == 1 for i in p if i != 1) and all(1 < gcd(D, i) < i for i in c) else -1


def lcm(n):
    x = n.copy()
    while x:
        i, n = x[-2:]
        del x[-2:]
        if not x: return n
        x.append(i * n // gcd(i, n))

from math import gcd
lcm = lambda x,y: x*y//gcd(x,y)

def DPC_sequence(s):
    res = 1
    for i,x in enumerate(s):
        if x == 'D':
            res = lcm(res, i+1)
    for i,x in enumerate(s):
        if (x == 'C' and (not res%(i+1) or gcd(res, i+1) == 1)) or (x == 'P' and gcd(res, i+1) > 1):
            return -1
    return res

from fractions import gcd
from functools import reduce

def DPC_sequence(s):
    ds, ps, cs, prod = [], [], [], 1
    
    for i, v in enumerate(s, 1):
        if v == 'D': 
            ds.append(i)
            prod = (prod * i) // gcd(prod, i)
        elif v == 'P': ps.append(i)
        elif v == 'C': cs.append(i)
    
    for p in ps: 
        if gcd(prod, p) != 1: return -1
    for c in cs: 
        if prod % c == 0 or gcd(prod, c) == 1: return -1
    
    return prod