ztx's Blog

/****************************************\
* Author : ztx
* Title  : [Hnoi2010]Bounce 弹飞绵羊
* ALG    : LCT
* CMT    :
* 对于i, 到i的绵羊会被弹到i+ki位置上, 那么我们连一条(i, i+ki)的边.
* 所有的关系建完之后, 就是一个森林, 而i位置被弹几次, 就是其深度.
* 这时设一个虚拟节点ROOT=n+1, 将森林里, 树的根都连在ROOT这个节点上,
* 那么所有的关系就是一颗树了.
* 在修改操作时, 先将u和u的父亲断开, 也就是cut操作,
* 再将u和u的新父亲连起来, 就是Link.
* 由于我们知道树的形态, 故可以免去换根操作
* Data   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [Hnoi2010]Bounce 弹飞绵羊
* ALG    : LCT
* CMT    :
* 对于i, 到i的绵羊会被弹到i+ki位置上, 那么我们连一条(i, i+ki)的边.
* 所有的关系建完之后, 就是一个森林, 而i位置被弹几次, 就是其深度.
* 这时设一个虚拟节点ROOT=n+1, 将森林里, 树的根都连在ROOT这个节点上,
* 那么所有的关系就是一颗树了.
* 在修改操作时, 先将u和u的父亲断开, 也就是cut操作,
* 再将u和u的新父亲连起来, 就是Link.
* 由于我们知道树的形态, 故可以免去换根操作
* Data   :
\****************************************/

#include <cstdio>

#define  maxn  200010LL
#define  null  0LL

int CH ;
void read(int& ret) {
     ret = 0 ; while (CH=getchar() , CH<'!') ;
     while (ret=ret*10+CH-'0' , CH=getchar() , CH>'!') ;
}

int fa[maxn] = {0} , ch[maxn][2] = {0} ;
int size[maxn] = {0} ;

#define left(u)    ch[u][0]
#define right(u)   ch[u][1]
#define min(a , b) (a)<(b)?(a):(b)

inline void Maintain(int u) {
	size[u] = size[left(u)]+size[right(u)]+1 ;
}

inline bool Isrt(int u) {
	return (!fa[u]) || ((left(fa[u])!=u)&&(right(fa[u])!=u)) ;
}

inline void zig(int x) {
    /* right rotate */
    int y = fa[x] , z = fa[y] ;
    if (left(z) == y) left(z) = x ; else if(right(z) == y) right(z) = x ; fa[x] = z ;
    fa[right(x)] = y ; left(y) = right(x) ; fa[y] = x ; right(x) = y ;
    Maintain(y) ;
}

inline void zag(int x) {
    /* left rotate */
    int y = fa[x] , z = fa[y] ;
    if (left(z) == y) left(z) = x ; else if(right(z) == y) right(z) = x ; fa[x] = z ;
    fa[left(x)] = y ; right(y) = left(x) ; fa[y] = x ; left(x) = y ;
    Maintain(y) ;
}

inline void Splay(int x) {
	int y , z ;
	while (!Isrt(x)) {
		y = fa[x] , z = fa[y] ;
		if (Isrt(y)) {
			if (left(y) == x) zig(x) ; else zag(x) ;
		} else {
			if (left(z) == y) {
				if (left(y) == x) zig(x) , zig(x) ;
				else zag(x) , zig(x) ;
			} else if (right(z) == y) {
				if (right(y) == x) zag(x) , zag(x) ;
				else zig(x) , zag(x) ;
			}
		}
	}
	Maintain(x) ;
}

inline void Access(int u) {
	for (int v = null ; u ; u = fa[u]) Splay(u) , right(u) = v , v = u , Maintain(u) ;
}

inline void Cut(int u , int v) {
    Access(u) , Splay(v) ; fa[v] = null ;
}

inline void Link(int u , int v) {
    Access(u) , Splay(u) ; right(u) = v , fa[v] = u ; Maintain(u) ;
}

inline int Query(int u) {
    Access(u) , Splay(u) ; return size[u]-1 ;
}

int n , m , i , j , k , cmd , ROOT , next , old_next ;
int K[maxn] ;

int main() {
	#define READ
	#ifdef  READ
		freopen("bzoj_2002.in" ,"r",stdin ) ;
		freopen("bzoj_2002.out","w",stdout) ;
	#endif
	read(n) ;
	for (i = 1 ; i <= n ; i ++ ) read(K[i]) ;
	ROOT = n+1 ;
	for (i = 1 ; i <= n+1 ; i ++ ) size[i] = 1 ;
	for (i = n ; i > 0 ; i -- ) {
        next = min(i+K[i] , ROOT) ; Link(next , i) ;
    }
    read(m) ;
	for (i = 1 ; i <= m ; i ++ ) {
		read(cmd) ;
		if (cmd == 1) {
            read(j) , j ++ ; printf("%d\n", Query(j) ) ;
		} else {
            read(j) , read(k) , j ++ ;
			old_next = min(K[j]+j , n+1) , next = min(k+j , n+1) ;
			Cut(old_next , j) , Link(next , j) ;
			K[j] = k ;
		}
	}
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}

/****************************************\
* Author : ztx
* Title  : bzoj 3720 Gty的妹子树
* ALG    : 分块
* CMT    :
* 我们用一次dfs过程将树分块.
* 首先, 定义根节点在块1中, 块1的size为1.
* 从根节点向下dfs, 对于当前点x, 依次遍历其儿子, 若遍历到儿子son时x所在的块的size小于Maxsize, 则将son加入x所在的块, x所在的块的size+1.
* 否则, 建立一个新块, 使son加入这个新块, 新块的size+1.
* 每遍历到一个儿子就向下dfs.
*
* 然后我们记录两个图, 一个是原来的树, 一个是块与块之间形成的图, 只需要在每次产生新块的时候加一条边即可.
* 不难发现, 块与块之间事实上形成的也是树形结构.
* 我们再对于每一个块记录下块内所有的权值, 并排序.
*
* 对于询问, 我们从当前节点向下dfs:
* 1.若遇到一个儿子不属于其所在的块, 则转到块与块之间形成的树向下搜索, 每遇到一个块就在块里二分找答案.
* 2.如果儿子依旧属于这个块, 那就直接看一下他和x的大小关系即可.
* 若令 Maxsize = sqrt(n), 这样的复杂度是O(sqrt(n)log(sqrt(n))).
* 对于加入新点, 我们直接在其父亲所在的块中加入一个点即可, 需要暴力修改权值的有序序列, 复杂度O(sqrt(n)).
* 当然如果父亲所在的块size达到了MAxsize, 就新建一个一个点的新块.
* 如果修改权值, 就直接在这个点所在的块的权值序列中暴力删除, 插入即可, 时间复杂度O(sqrt(n)).
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : bzoj 3720 Gty的妹子树
* ALG    : 分块
* CMT    :
* 我们用一次dfs过程将树分块.
* 首先, 定义根节点在块1中, 块1的size为1.
* 从根节点向下dfs, 对于当前点x, 依次遍历其儿子, 若遍历到儿子son时x所在的块的size小于Maxsize, 则将son加入x所在的块, x所在的块的size+1.
* 否则, 建立一个新块, 使son加入这个新块, 新块的size+1.
* 每遍历到一个儿子就向下dfs.
*
* 然后我们记录两个图, 一个是原来的树, 一个是块与块之间形成的图, 只需要在每次产生新块的时候加一条边即可.
* 不难发现, 块与块之间事实上形成的也是树形结构.
* 我们再对于每一个块记录下块内所有的权值, 并排序.
*
* 对于询问, 我们从当前节点向下dfs:
* 1.若遇到一个儿子不属于其所在的块, 则转到块与块之间形成的树向下搜索, 每遇到一个块就在块里二分找答案.
* 2.如果儿子依旧属于这个块, 那就直接看一下他和x的大小关系即可.
* 若令 Maxsize = sqrt(n), 这样的复杂度是O(sqrt(n)log(sqrt(n))).
* 对于加入新点, 我们直接在其父亲所在的块中加入一个点即可, 需要暴力修改权值的有序序列, 复杂度O(sqrt(n)).
* 当然如果父亲所在的块size达到了MAxsize, 就新建一个一个点的新块.
* 如果修改权值, 就直接在这个点所在的块的权值序列中暴力删除, 插入即可, 时间复杂度O(sqrt(n)).
* Time   :
\****************************************/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std ;

#define  maxn  60010LL
#define  masz  210LL

int n , fa[maxn] = {0} ;
int data[maxn] , belong[maxn] , blccnt = 0 ;
int blc[maxn][masz] , siz[maxn] = {0} , blcsiz = 0 ;

vector<int> G[maxn] , Bc[maxn] ;

void Dfs(int u , int tp) {
int i ;
    int from = belong[u] ;
    blc[from][++siz[from]] = data[u] ;
    fa[u] = tp ;
    for (i = 0 ; i < G[u].size() ; i ++ )
        if (G[u][i] != tp) {
            if (siz[from] < blcsiz) belong[G[u][i]] = from ;
            else {
                belong[G[u][i]] = ++blccnt ;
                Bc[from].push_back(blccnt);
            }
            Dfs(G[u][i] , u) ;
        }
}
int Find(int u , int w) {
    int tmp = upper_bound(blc[u]+1 , blc[u]+siz[u]+1 , w)-blc[u]-1 ;
    return siz[u]-tmp ;
}

int QueryBlc(int u , int w) {
int i ;
    int ret = Find(u , w) ;
    for (i = 0 ; i < Bc[u].size() ; i ++ ) ret += QueryBlc(Bc[u][i] , w) ;
    return ret ;
}

int Query(int u , int tp , int w) {
int i ;
    int ret = data[u]>w ? 1 : 0 ;
    for (i = 0 ; i < G[u].size() ; i ++ )
        if (G[u][i] != tp) {
            if (belong[G[u][i]] == belong[u]) ret += Query(G[u][i] , u , w) ;
            else ret += QueryBlc(belong[G[u][i]] , w) ;
        }
    return ret ;
}

void Insert(int tp , int w) {
    int from = belong[tp] ;
    fa[++n] = tp , data[n] = w ;
    G[tp].push_back(n) , G[n].push_back(tp) ;
    if (siz[from] < blcsiz) {
        blc[belong[n] = from][++siz[from]] = data[n] ;
        sort(blc[from]+1 , blc[from]+siz[from]+1) ;
    } else {
        Bc[from].push_back(belong[n] = ++blccnt) ;
        blc[blccnt][++siz[blccnt]] = data[n] ;
    }
}

void Change(int u , int w) {
int i ;
    int from = belong[u] ;
    for (i = 1 ; i <= siz[from] ; i ++ )
        if (blc[from][i] == data[u]) {
            blc[from][i] = data[u] = w ;
            break ;
        }
    sort(blc[from]+1 , blc[from]+siz[from]+1) ;
}

void BuildBlc() {
int from ;
    blcsiz = (int)sqrt(n+0.5+log(n)/log(2)) ;
    belong[1] = ++blccnt ;
    Dfs(1 , 0) ;
    for (from = 1 ; from <= blccnt ; from ++ )
        sort(blc[from]+1 , blc[from]+siz[from]+1) ;
}

int main() {
int i , u , v , m , cmd , LAST = 0 ;
//  #define READ
    #ifdef  READ
        freopen(".in" ,"r",stdin ) ;
        freopen(".out","w",stdout) ;
    #endif
    scanf("%d", &n) ;
    for (i = 1 ; i < n ; i ++ ) {
        scanf("%d%d", &u , &v) ;
        G[u].push_back(v) , G[v].push_back(u) ;
    }
    for (u = 1 ; u <= n ; u ++ )
        scanf("%d", &data[u]) ;
    BuildBlc() ;
    scanf("%d", &m) ;
    for (i = 1 ; i <= m ; i ++ ) {
        scanf("%d%d%d", &cmd , &u , &v) ;
        u ^= LAST , v ^= LAST ;
        if (cmd == 0) printf("%d\n", LAST = Query(u , fa[u] , v)) ;
        else if (cmd == 1) Change(u , v) ;
        else Insert(u , v) ;
    }
    #ifdef  READ
        fclose(stdin) ; fclose(stdout) ;
    #else
        getchar() ; getchar() ;
    #endif
    return 0 ;
}

/****************************************\
* Author : ztx
* Title  : [HAOI2008]移动玩具
* ALG    : 搜索 + hash剪枝
* CMT    :
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [HAOI2008]移动玩具
* ALG    : 搜索 + hash剪枝
* CMT    :
* Time   :
\****************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std ;

#define  maxs  65536LL

const int dx[4] = {0 , 0 , 1 , -1} ,
          dy[4] = {1 , -1 , 0 , 0} ;

struct data { bool a[5][5] ; int step ; } q[maxs] ;

int Start , End , h ;
bool ans[5][5] , exist[maxs] ;

int hash(bool a[5][5]) {
    int k = 1 , s = 0 , i , j ;
    for (i = 1 ; i < 5 ; i ++ )
        for (j = 1 ; j < 5 ;j ++ )
            s += k*a[i][j] , k <<= 1 ;
    return s ;
}

int main() {
//  #define READ
    #ifdef  READ
        freopen(".in" ,"r",stdin ) ;
        freopen(".out","w",stdout) ;
    #endif
    int t = 0 , w = 1 , i , j , k , x , y ;
    char ch[5] ;
    for (i = 1 ; i < 5 ; i ++ ) {
        scanf("%s", ch) ;
        for(j = 1 ; j <= 4 ; j ++ )
           q[0].a[i][j] = ch[j-1]-'0' ;
    }
    for(i = 1 ; i <= 4 ; i ++ ) {
        scanf("%s",ch);
        for(j = 1 ; j <= 4 ; j ++ )
           ans[i][j] = ch[j-1]-'0' ;
    }
    Start = hash(q[t].a) ;
    End = hash(ans) ;
    if (Start == End) {
        puts("0") ; goto END ;
    }
    exist[Start] = 1 ;
    while (t < w) {
        for(i = 1 ; i < 5 ; i ++ )
            for (j = 1 ; j < 5 ; j ++ ) if (q[t].a[i][j])
                for (k = 0 ; k < 4 ; k ++ ) {
                    x = i+dx[k] , y = j+dy[k] ;
                    if (q[t].a[x][y] || x>4 || y>4 || x<1 || y<1) continue ;
                    swap(q[t].a[i][j] , q[t].a[x][y]) ;
                    h = hash(q[t].a) ;
                    if (!exist[h]) {
                        if (h == End) {
                            printf("%d", q[t].step+1) ; goto END ;
                        }
                        exist[h] = 1 ;
                        memcpy(q[w].a , q[t].a , sizeof q[w].a) ;
                        q[w].step = q[t].step+1 ;
                        w ++ ;
                    }
                    swap(q[t].a[i][j] , q[t].a[x][y]) ;
                }
        t ++ ;
    }
    END : ;
    #ifdef  READ
        fclose(stdin) ; fclose(stdout) ;
    #else
        getchar() ; getchar() ;
    #endif
    return 0 ;
}

/****************************************\
* Author : ztx
* Title  : [ZJOI2006]物流运输trans
* ALG    : 最短路 dp
* CMT    : dp(i) = min(length(1,i)*i , dp(j)+length(j+1,i)*(i-j)+k) ;
*          { 1 <= j < i }
*          length(i,j)表示从第 i 天到第 j 天走同一条道路的最短路径长度
*          特别注意，一个点有可能有多个时间段不能通过 = =
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [ZJOI2006]物流运输trans
* ALG    : 最短路 dp
* CMT    : dp(i) = min(length(1,i)*i , dp(j)+length(j+1,i)*(i-j)+k) ;
*          { 1 <= j < i }
*          length(i,j)表示从第 i 天到第 j 天走同一条道路的最短路径长度
*          特别注意，一个点有可能有多个时间段不能通过 = =
* Time   :
\****************************************/

#include <cstdio>

int CH , NEG ;

template<typename T>
inline void read(T& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

typedef long long ll ;

#include <cstring>

#define  maxn  105LL
#define  maxm  25LL
#define  maxd  10010LL
#define  info  0x7f7f7f7f7f7f7f7fLL
/* maxd 坑死人 = = */

int n , m , u , v ;
ll K ;
ll f[maxn] = {0} ;
ll length[maxn][maxn] = {0} ;

ll map[maxm][maxm] = {0} ;
ll dis[maxm] = {0} ;
bool inq[maxm] = {0} ;
int cont_time[maxd][3] = {0} ;
bool cont[maxm] = {0} ;

#define  sizeque  100LL
int q[sizeque] , head , tail ;
inline int F(int x) { return ((x%sizeque)+sizeque)%sizeque ; }
inline void clear() { head = 0 , tail = -1 ; }
inline int front() { return q[F(head)] ; }
inline int back() { return q[F(tail)] ; }
inline void push_front(int x) { q[F(--head)] = x ; }
inline void push_back(int x) { q[F(++tail)] = x ; }
inline void pop_front() { head ++ ;}
inline void pop_back() { tail -- ; }
inline bool empty() { return head > tail ; }

void SPFA(int start , int end) {
    memset(cont , 0 , sizeof cont) ;
    memset(dis , 0x7f , sizeof dis) ; clear() ;
    for (u = 1 ; u <= cont_time[0][0] ; u ++ ) {
        if (cont_time[u][1]>end || cont_time[u][2]<start) continue ;
        else cont[cont_time[u][0]] = true ;
    }
    push_back(1) ; inq[1] = true ; dis[1] = 0 ;
    while (!empty()) {
        u = front() , pop_front() ; inq[u] = false ;
        for (v = 1 ; v <= m ; v ++ ) {
            if (map[u][v]==info || cont[v]) continue ;
            if (dis[v] > dis[u]+map[u][v]) {
                dis[v] = dis[u]+map[u][v] ;
                if (!inq[v]) {
                    inq[v] = true ;
                    if (!empty() && dis[v]<dis[front()]) push_front(v) ;
                    else push_back(v) ;
                }
            }
        }
    }
    if (dis[m] == info) length[start][end] = -1 ;
    else length[start][end] = dis[m] ;
}

int i , j ;
ll tmp ;
int main() {
//  #define READ
    #ifdef  READ
        freopen(".in" ,"r",stdin ) ;
        freopen(".out","w",stdout) ;
    #endif
    read(n) , read(m) , read(K) , read(i) ;
    memset(map , 0x7f , sizeof map) ;
    while (i -- ) {
        read(u) , read(v) , read(tmp) ;
        if (map[u][v] > tmp) { map[u][v] = map[v][u] = tmp ; }
    }
    read(cont_time[0][0]) ;
    for (i = 1 ; i <= cont_time[0][0] ; i ++ ) {
        read(cont_time[i][0]) , read(cont_time[i][1]) , read(cont_time[i][2]) ;
    }
    for (i = 1 ; i <= n ; i ++ )
        for (j = i ; j <= n ; j ++ )
            SPFA(i , j) ;
    memset(f , 0x7f , sizeof f) ;
    f[0] = -K ;
    for (i = 1 ; i <= n ; i ++ ) {
        for (j = 0 ; j < i ; j ++ ) {
            if (f[j]==info || length[j+1][i]<0) continue ;
            tmp = f[j]+(ll)K+(ll)length[j+1][i]*(ll)(i-j) ;
            if (tmp < f[i]) f[i] = tmp ;
        }
    }
    printf("%lld\n", f[n] ) ;
    #ifdef  READ
        fclose(stdin) ; fclose(stdout) ;
    #else
        getchar() ; getchar() ;
    #endif
    return 0 ;
}

/****************************************\
* Author : ztx
* Title  : [Noi2010]能量采集
* ALG    :
* CMT    :
* 位于 (x,y) 的点产生的分值是 gcd(x,y) , 问题转换为求 gcd(x,y) , 答案为 Σ(gcd(x,y)*2-1)
* 考虑 gcd(x,y)=D , D<=10^5 范围不是很大 , 那么我们倒过来考虑 , 我们求解满足 gcd(x,y)=d 的 (x,y) 的个数.
* 有 Σ(gcd(x,y)*2-1) = Σ(F[d]*(d*2-1)) ;
* 其中 F[d] 表示满足 gcd(x,y)=d 的 (x,y) 的个数.
* 考虑以d为公约数的(x,y)的个数g[d]，显然有g[d]=[n/d]*[m/d] ;
* 根据容斥原理有：
* f[d]=g[d]-Σ(f[d*i])  (2<=i<=[min(n,m)/d]) ;
* 这样我们只需要倒过来从min(n,m)反推到1求解即可.
* 时间复杂度O(nlogn)
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [Noi2010]能量采集
* ALG    :
* CMT    :
* 位于 (x,y) 的点产生的分值是 gcd(x,y) , 问题转换为求 gcd(x,y) , 答案为 Σ(gcd(x,y)*2-1)
* 考虑 gcd(x,y)=D , D<=10^5 范围不是很大 , 那么我们倒过来考虑 , 我们求解满足 gcd(x,y)=d 的 (x,y) 的个数.
* 有 Σ(gcd(x,y)*2-1) = Σ(F[d]*(d*2-1)) ;
* 其中 F[d] 表示满足 gcd(x,y)=d 的 (x,y) 的个数.
* 考虑以d为公约数的(x,y)的个数g[d]，显然有g[d]=[n/d]*[m/d] ;
* 根据容斥原理有：
* f[d]=g[d]-Σ(f[d*i])  (2<=i<=[min(n,m)/d]) ;
* 这样我们只需要倒过来从min(n,m)反推到1求解即可.
* 时间复杂度O(nlogn)
* Time   :
\****************************************/

#include <cstdio>

#define  maxn     100010LL
#define  min(x,y) ((x)<(y)?(x):(y))

typedef long long ll ;

int n , m , i , j , k ;
ll f[maxn] = {0} , ans ;

int main() {
	#define READ
	#ifdef  READ
		freopen("energy2010.in" ,"r",stdin ) ;
		freopen("energy2010.out","w",stdout) ;
	#endif
	scanf("%d%d", &n , &m ) ;
	k = min(n,m) ;
	for (i = k ; i >= 1 ; i -- ) {
		f[i] = (ll)(n/i)*(ll)(m/i) ;
		for (j = 2 ; j <= k/i ; j ++ ) f[i] -= f[i*j] ;
		ans += f[i]*(ll)(i*2-1) ;
	}
	printf("%lld\n", ans ) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}

/****************************************\
* Author : ztx
* Title  : [HNOI2012]排队
* ALG    :
* CMT    :
    1 首先不考虑两个老师相邻的情况,即将老师看做男生,
      再用隔板法得到此时的方案数为
          P(n+2,n+2)*A(n+3,m)*P(m,m)
    2 再找出两个老师相邻的方案数.将两个老师看做一个人,
      再用隔板法得到方案数为
          P(n+1,n+1)*P(2,2)*A(n+2,m)*P(m,m)
    3 将两个数相减得到答案,最终化简为
          ans = (n*n+3*n+2*m) * Π(1,n+1) * Π(n-m+4,n+2)
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [HNOI2012]排队
* ALG    :
* CMT    :
    1 首先不考虑两个老师相邻的情况,即将老师看做男生,
      再用隔板法得到此时的方案数为
          P(n+2,n+2)*A(n+3,m)*P(m,m)
    2 再找出两个老师相邻的方案数.将两个老师看做一个人,
      再用隔板法得到方案数为
          P(n+1,n+1)*P(2,2)*A(n+2,m)*P(m,m)
    3 将两个数相减得到答案,最终化简为
          ans = (n*n+3*n+2*m) * Π(1,n+1) * Π(n-m+4,n+2)
* Time   :
\****************************************/

#include <cstdio>
#include <cstring>

typedef long long ll ;

#define  max(x,y) ((x)>(y)?(x):(y))
#define  hpsize   10000LL
#define  width    10000LL

struct HP {
	int size ;
	int a[hpsize] ;
	HP() { size = 1 ; a[1] = 0 ; }
	void Assign(int x) { size = 0 ; while (x) { a[++size] = x%width ; x /= width ; } }
	HP operator * (const int b) const {
		HP ret ;
		int i , x = 0 ;
		for (i = 1 ; i <= size ; i ++ ) ret.a[i] = a[i]*b ;
		for (ret.size = 1 ; ret.size<=size || x ; ret.size ++ ) {
			ret.a[ret.size] += x ;
			x = ret.a[ret.size]/width ;
			ret.a[ret.size] %= width ;
		}
		while (!ret.a[ret.size] && ret.size>1) ret.size -- ;
		return ret ;
	}
	void Print() {
	    printf("%d", a[size]);
	    for (int i = size-1 ; i > 0 ; i -- ) printf("%04d", a[i] ) ;
	}
} ;

HP ans ;
int n , m , i ;

int main() {
	#define READ
	#ifdef  READ
		freopen("bzoj_2729.in" ,"r",stdin ) ;
		freopen("bzoj_2729.out","w",stdout) ;
	#endif
	scanf("%d%d", &n , &m ) ;
	if (m > n+3) { putchar('0') ; goto END ; }
	ans.Assign(n*n+3*n+2*m) ;
	for (i = 1 ; i <= n+1 ; i ++ ) ans = ans*i ;
	for (i = n-m+4 ; i <= n+2 ; i ++ ) ans = ans*i ;
	ans.Print() ;
	END : ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}

/****************************************\
* Author : ztx
* Title  : [Cqoi2010]扑克牌
* ALG    : 二分
* CMT    :
* 首先二分答案,设组成的套数为M,
* 在判断是否成立时 , 枚举每一个c , 若ci<M , 则用joker补,
* 使用的joker必须要小于等于min(m,M)
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [Cqoi2010]扑克牌
* ALG    : 二分
* CMT    :
* 首先二分答案,设组成的套数为M,
* 在判断是否成立时 , 枚举每一个c , 若ci<M , 则用joker补,
* 使用的joker必须要小于等于min(m,M)
* Time   :
\****************************************/

#include <cstdio>

#define  maxn  55LL
#define  maxc  1000000000LL

int n , m , i ;
int c[maxn] ;
int cnt ;

inline bool Could(int M) {
	cnt = 0 ;
	for (i = 1 ; i <= n ; i ++ ) {
		if (c[i] < M) cnt += M-c[i] ;
		if (cnt > M || cnt > m) return false ;
	}
	return true ;
}

int L , R , M ;
inline int Bsearch() {
	L = 0 , R = maxc+1 ;
	while (R-L > 1) {
		/* [L , R) */
		M = L+(R-L)/2 ;
		if (Could(M)) L = M ;
		else R = M ;
	}
	return L ;
}

int main() {
//	#define READ
	#ifdef  READ
		freopen(".in" ,"r",stdin ) ;
		freopen(".out","w",stdout) ;
	#endif
	scanf("%d%d", &n , &m ) ;
	for (i = 1 ; i <= n ; i ++ ) scanf("%d", &c[i] ) ;
	printf("%d\n", Bsearch() ) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}

/****************************************\
* Author : ztx
* Title  : poj 3335 Rotating Scoreboard
* ALG    : 计算几何 半平面交 多边形内核
* CMT    : 这是一个n^n算法
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : poj 3335 Rotating Scoreboard
* ALG    : 计算几何 半平面交 多边形内核
* CMT    :
* Time   :
\****************************************/

#include <cstdio>

#define  maxn 105LL

struct POINT {
	double x , y ;
	POINT operator - (const POINT& b) const { return (POINT){x-b.x , y-b.y} ; }
	int operator * (const POINT& b) const { return x*b.y-y*b.x ; }
} p[maxn] , sta[maxn] , points[maxn] ;
/* points[]存储原数据 , sta缓存 , p为已经存在的半平面交的顶点 */
typedef POINT VECTOR ;
VECTOR Vector(POINT from , POINT to) { return to-from ; }

int n , size , top ;

POINT Intersect(POINT a , POINT b , POINT c , POINT d) {
	/* 传进四个点时,保证有交点 */
	POINT ret ;
	if (a.x == b.x) {
		ret.x = a.x ; ret.y = (c.y+d.y)/2.0 ;
	} else if (c.x == d.x) {
		ret.x = c.x ; ret.y = (a.y+b.y)/2.0 ;
	} else {
		ret.x = ((c.x-d.x)*(a.y*b.x-a.x*b.y)-(a.x-b.x)*(c.y*d.x-c.x*d.y))
				/((d.y-c.y)*(a.x-b.x)-(b.y-a.y)*(c.x-d.x)) ;
		ret.y = (ret.x*(b.y-a.y)+a.y*b.x-a.x*b.y)/(b.x-a.x) ;
	}
	return ret ;
}

int Direct(POINT from , POINT to , POINT p) {
	int tmp = (to-from)*(p-to) ;
	if (tmp < 0) return -1 ; else return tmp > 0 ;
	/* 左侧为1 , 同向为0 , 右侧为-1 */
}

void Cut(POINT a , POINT b) {
int i ;
	top = 0 ;
	for (i = 1 ; i <= size ; i ++ ) {
		/* 若点以顺时针给出 */
		if (Direct(a , b , p[i]) <= 0)
			sta[++top] = p[i] ;
		else {
			if (Direct(a , b , p[i-1]) < 0)
				sta[++top] = Intersect(a , b , p[i-1] , p[i]) ;
			if (Direct(a , b , p[i+1]) < 0)
				sta[++top] = Intersect(a , b , p[i] , p[i+1]) ;
		}
	}

	for (i = 1 ; i <= top ; i ++ ) p[i] = sta[i] ;
	p[0] = p[top] ;
	p[top+1] = p[1] ;
	size = top ;
}

bool Solve() {
	for (int i = 1 ; i <= n ; i ++ )
		Cut(points[i] , points[i+1]) ;
	return size > 0 ;
}

int main() {
int T , i ;
//	#define READ
	#ifdef  READ
		freopen(".in" ,"r",stdin ) ;
		freopen(".out","w",stdout) ;
	#endif
	scanf("%d", &T ) ;
	while (T --) {
		scanf("%d", &n ) ;
		for (i = 1 ; i <= n ; i ++ )
			scanf("%lf%lf", &points[i].x , &points[i].y) ;
		points[n+1] = points[1] ;
		points[0] = points[n] ;
		for (i = n+1 ; i >= 0 ; i -- ) p[i] = points[i] ;
		size = n ;
		if (Solve()) puts("YES") ;
		else puts("NO") ;
	}
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}

/****************************************\
* Author : ztx
* Title  : [SHOI2008]汉诺塔
* ALG    : 递推
* CMT    :

先解决子问题,把 x 柱上的 i-1 个圆盘移走,再把第 i 个大圆盘移走.
设y = to[x][i-1] , z = 0+1+2-y-x (即除 x , y 以外的柱子编号)
即 1)x 上 i-1 个圆盘移至 y 上
   2)将 x 上的第 i 个圆盘移至z
这时:
   若 f[y][i-1] = z :
      3)直接移到z结束
      此情况: f[x][i] = f[x][i-1]+1+f[y][i-1] , to[x][i] = z
   若 f[y][i-1] = x :
      3)i-1 个圆盘移至 x
      4)将 z 上的第 i 个圆盘移至 y
      5)x 上 i-1 个圆盘移至y结束
      此情况: f[x][i] = f[x][i-1]+1+f[y][i-1]+1+f[x][i-1] , to[x][i] = y
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [SHOI2008]汉诺塔
* ALG    : 递推
* CMT    :

先解决子问题,把 x 柱上的 i-1 个圆盘移走,再把第 i 个大圆盘移走.
设y = to[x][i-1] , z = 0+1+2-y-x (即除 x , y 以外的柱子编号)
即 1)x 上 i-1 个圆盘移至 y 上
   2)将 x 上的第 i 个圆盘移至z
这时:
   若 f[y][i-1] = z :
      3)直接移到z结束
      此情况: f[x][i] = f[x][i-1]+1+f[y][i-1] , to[x][i] = z
   若 f[y][i-1] = x :
      3)i-1 个圆盘移至 x
      4)将 z 上的第 i 个圆盘移至 y
      5)x 上 i-1 个圆盘移至y结束
      此情况: f[x][i] = f[x][i-1]+1+f[y][i-1]+1+f[x][i-1] , to[x][i] = y
* Time   :
\****************************************/

#include <cstdio>

#define  maxn  50LL

typedef long long ll ;

int n ;
int ope[10][2] = {0} ;

ll f[4][maxn] = {0} ;
int to[4][maxn] = {0} ;

int i , CH , x , y , z ;
int main() {
//	#define READ
	#ifdef  READ
		freopen(".in" ,"r",stdin ) ;
		freopen(".out","w",stdout) ;
	#endif
	scanf("%d", &n ) ;
	for (i = 0 ; i < 6 ; i ++ ) {
		while (CH=getchar() , CH<'!') ;
		ope[i][0] = CH-'A' ; ope[i][1] = getchar()-'A' ;
	}
    for (x = 0 ; x < 3 ; x ++ )
        for (i = 0 ; i < 6 ; i ++ )
            if (ope[i][0] == x) {
                f[x][1] = 1 ;
                to[x][1] = ope[i][1] ;
                break ;
            }
	for (i = 2 ; i <= n ; i ++ )
	    for (x = 0 ; x < 3 ; x ++ ) {
			y = to[x][i-1] ; z = 3-x-y ;
			if (to[y][i-1] == z) to[x][i] = z , f[x][i] = f[x][i-1]+1+f[y][i-1] ;
			else to[x][i] = y , f[x][i] = f[x][i-1]+1+f[y][i-1]+1+f[x][i-1] ;
		}
	printf("%lld\n", f[0][n] ) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}