def binary_search(arr,item):
    #二分查找
    l,h=0,len(arr)-1
    while l<h:
        mid=(l+h)//2
        if arr[mid]<item:
            l = mid + 1
        elif arr[mid]>item:
            h=mid-1
        else:
            return  mid
    return None

def selectsort(arr):
    #选择排序
    n=len(arr)
    if n<2:return 
    start=0
    while start<n:
        res=[]
        index=start
        #每次找剩下的最小值
        for i in range(start+1,len(arr)):
            if arr[i] < arr[index]:
                index=i
            
        t=arr[index]
        arr[index]=arr[start]
        arr[start]=t
        start+=1


def quicksort(arr):
    #快速排序
    if len(arr)<2:return arr
    else:
        pivot=arr[0]
        #每次把序列分成小于基准和大于基准的
        less=[i for i in arr[1:] if i<=pivot]
        greator=[i for i in arr[1:] if i >pivot]
        return quicksort(less) + [pivot]+ quicksort(greator)

        
def bfs(node,target):
    #查找路径是否存在
    from collections import deque
    search_queue=deque()
    searched=[]
    search_queue.append(name)
    while search_queue:
        p=search_queue.popleft()
        if p not in searched:
            if p == target:
                return True
            else:
                search_queue.append(p.next)
                searched.append(p)
    return False

    
class Node:
   
    def __init__(self,x,y,step):
        self.x=x
        self.y=y
        self.step=step
        pass


def bfs(Arr,target):
    #走迷宫问题
    from collections import deque
    r=len(Arr)
    c=len(Arr[0])
    visit=Arr[None]*c
    for i in range(r):
        visti[i]=[0]*r
    
    step=[[-1,0],[1,0],[0,-1],[0,1]]
    q=deque()
    q.append(Node(0,0,0))
    while q:
        cur=q.popleft()
        if cur.x==target[0] and cur.y==target[1]:
            return cur.step
        for i in step:
            nr=cur[0]+i[0]
            nc=cur[1]+i[1]
            if nr>=0 and nc>=0 and nr<r and nc<c and visit[nr][nc]==0:
                visit[nr][nc]=steps
                if Arr[nr][nc]==1:#能走加入队列累加步数
                    q.append(Node(nr,nc,cur.step+1))

    return 0


def dp(dicstuf,bag):
    #动态规划 背包问题
    #dicstruf 一组二位数组，[[1,2]]  第一位表示重量，第二位表示价值
    cell=[None]*len(dicstuf)
    for i in range(len(dicstuf)):
        cell[i]=[0]*bag
    
    for i in len(dicstuf):
        for j in bag:
            if i==0 and dicstuf[i][0]<j:
                cell[i][j]=dicstuf[i][1]
            else:
                if dicstuf[i][0]<j:# 比较上一个单元格和当前单元格放了当前商品+剩余价值
                    cell[i][j]=max(cell[i-1][j],cell[i-1][j-dicstuf[i][0]])
                else:
                    cell[i][j]=cell[i-1][j]

    return cell[-1][-1]

def dfs(nums,k):
    #部分求和问题， nums为数字序列，k为和，求一个序列和为k
    #类似与二叉树求路径和为k的路径，nums又n个数，构建n层的完全二叉树，根节点    
    #为0，每个左节点为0，右子节点为nums[c]，c为层数，然后遍历所有路径求路径和为k的路径就是的··· 前边有一次做的lintcode题目就是这个·
    res=[]
    def dfssum(i,sum):
        if i >=len(nums):
            return sum==k
        if sum>k:
            return False
        if dfssum(i+1,sum):
            return True
        if dfssum(i+1,sum+nums[i]):
            res.append(nums[i])
            return True
        return False

    if dfssum(0,0):return res
    return []