You are given the following :-

— An array A of length N
— An integer X

Task

Determine the number of sub-sequences of Array A such that the following condition is satisfied.

— If i1,i2....ik is the indices in the sub-sequence, then ( A[i1] ^ A[i2] ^.....^A[ik] ) & X =0, where ^ represents Bitwise XOR and & represent Bitwise AND operator.

Since, the number of sub-sequences can be large enough, output it modulo 10^9+7.

Example:-

Assumptions

• N = 4
• X = 7
• A[] = [5,2,7,6]

Output:-
2 , one is [5,2,7] another Empty sub-sequence.

Constraints

• 1<= N <= 1000
• 1<= X <= 1000
• 0<= A[i] <= 1000

Sample Input:-
3
1
5 7 1

Sample Output:-
4

Given a list that contains N strings of lowercase English alphabets. Any number of contiguous strings can be found together to form a new string. The grouping function accepts two integers X and Y and concatenates all strings between indices X and Y (inclusive) and returns a modified string in which the alphabets of the concatenated string are sorted.

You are asked Q questions each containing two integers L and R. Determine the K th. character in the concatenated string if we pass L and R to the grouping function.

Note: It is always guaranteed that the Kth position is valid

Input Format

• First Line: N(number of strings in the list)
• Next N lines: String s_i
• Next line Q(number of questions)
• Next Q lines : Three space-separated integers L, R and K

Output Format

For each question, print the K th character of the concatenated string in a new line.

Sample Test Cases

Sample Input

• 5
• aaaaa
• bbbb
• cccccd
• eeeee
• ddddd
• 3
• 3 3 3
• 1 5 16
• 3 5 15

Sample Output

• c
• d
• e

Explanation

• Q1 Grouped String cccccd. 3rd character is c
• Q2 Grouped String aaaaabbbbcccccddddddeeeee. 16th character is d
• Q3 Grouped String cccccddddddeeeee. 15th character is e

Input

• 5
• zpqrs
• efghi
• jklmn
• abcde
• 2
• 3 3 3
• 1 5 6

Output

• g
• f

Solution of this problem with complexity O(NQ) is trivial. Is it possible to solve this question with complexity better than O(NQ)

Given a bit string S i.e containing "0" and "1" only. You can perform K number of operations (K>0) in an iterative way, always starting from K=1, in the following manner:-

when K=1, remove one leftmost bit and append it to right.
when K=2, remove two leftmost bit one by one and append it to right one by one.
when K=3, remove three left most bit one by one and append it to right one by one.
when K=4, remove four left most bit one by one and append it to right one by one.
so on...

You have to print the minimum value of K (K > 0) so that we get our original input string S after K number of operations.

Input format :-

A sigle string S.

Output format :-

Print minimum value of K.

Constraints:-

2<=length of string<=10^5

Example:-

Input 1:-

1011

Output:-

7

Input 2:-

1101

Output:-

7

Input 3:-

11011

Output:-

4

Input 4:-

11010

Output:-

4

Input 5:-

01010

Output:-

4

Input 6:-

101010

Output:-

3

Input 7:-

111001

Output:-

3

Explanations:-

In 1st input S=1011, so starting from K=1,

K=1 , S=0111 (1011 -> 0111)
K=2 , S=1101 (0111 -> 1110 -> 1101)
K=3 , S=1110 (1101 -> 1011 -> 0111 -> 1110)
K=4 , S=1110 (1110 -> 1101 -> 1011 -> 0111 -> 1110)
K=5 , S=1101 (1110 -> 1101 -> 1011 -> 0111 -> 1110 -> 1101)
K=6 , S=0111 (1101 -> 1011 -> 0111 -> 1110 -> 1101 -> 1011 -> 0111)
K=7 , S=1011 (0111 -> 1110 -> 1101 -> 1011 -> 0111 -> 1110 -> 1101 -> 1011)

so answer is K=7.

You are given a tree of A nodes having A-1 edges.Each node is numbered from 1 to A where 1 is root of tree. You are given Q queries. In each query, you will be given a unique integer j. You are required to remove the jth numbered edge from the tree. This operation will divide a tree into two different trees. For each query once you perform the remove operation you are asked to tell the maximum size among the sizes of the trees present till that query.

Note:-

1. once an edge is removed it will be considered removed for all the further queries.
2. it is guaranteed that each edge will be printing to exactly two different nodes of tree.
3. edges are numbered from 1 to A-1.

Input format:-

• first line input argument are an integer A denoting the number of nodes and an integer Q denoting number of queries.
• second & third argument are the integer arrays B & C where for each i (0 <= i <= A-1) , i denotes the (i+1)th edge and B[i] & C[i] are the nodes connected by it.
• fourth argument is an integer array D of distinct elements where D[i] denotes the number of edges to be removed for the ith query.

Output:-
print answers for each query.

Constraints:-

2<= A <= 10^5
1<= B[i] , C[i] <=A
1<= D[i] , Q <=A-1

Example:-

Input:
5 2
1 3 3 5
3 2 4 1
1 3

Output:-
3 2

Given a tree T containing N nodes numbered [1,2..,N] rooted at node 1 . Each edge has a value associated with it.You are also given a number K. You need to find the maximum weight you can collect in K-steps .When you traverse an edge, it is counted as 1 step.

Note:
1. you should start from root node.
2. you can traverse an edge from parent to child or child to parent.
3. you can traverse an edge multiple times.
4. weights of edges are always positive integer.

Constraints:
0<=K<=1000000
0<=N<=500000
0<=weights<=1000000000

Input format:

1. first line contain N,K i.e number of nodes, number of steps respectively.
2. next N-1 lines contain three integers a,b,c i.e there is an edge between 'a' and 'b' with weight 'c'.

Output format:

maximum weight collected in K-steps.

Example:-
Input:
6 3
1 2 5
1 3 6
2 4 15
2 5 1
3 6 11

Output: 35

Explanation:

Traversal for max. weight collection: [1-2-4-2]. Thus weight collected 5+15+15=35

How to solve this question? Plz Help. Thanks in advance.